530.二叉搜索树的最小绝对差
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 28526、弹幕量 339、点赞数 604、投硬币枚数 390、收藏人数 116、转发人数 39, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数，你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树，单调队列正式登场！| LeetCode：239. 滑动窗口最大值，手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找，又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树，不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索，帮你拿下反转链表 | LeetCode：206.反转链表 | 双指针法 | 递归法，关于二叉树，你该了解这些！| 二叉树理论基础一网打尽，二叉树的种类、二叉树的存储方式、二叉树节点定义、二叉树的遍历顺序，要理解普通二叉树和完全二叉树的区别！ | LeetCode：222.完全二叉树节点的数量，新学期要从学习二叉树开始！ | LeetCode：101. 对称二叉树
https://www.bilibili.com/video/BV1DD4y11779
思路：中序遍历，用一个指针指向上一个节点，然后比较。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {TreeNode pre = null;int min = Integer.MAX_VALUE;public int getMinimumDifference(TreeNode root) {getMinAbs(root);return min;}public void getMinAbs(TreeNode root) {if (root == null) {return;}getMinimumDifference(root.left);if (pre != null) {min = Math.min(min,Math.abs(root.val-pre.val));}pre = root;getMinimumDifference(root.right);}
}501.二叉搜索树中的众数
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 79660、弹幕量 487、点赞数 1515、投硬币枚数 836、收藏人数 1180、转发人数 90, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：二叉搜索树中，需要掌握如何双指针遍历！| LeetCode：530.二叉搜索树的最小绝对差，调整二叉树的结构最难！| LeetCode：450.删除二叉搜索树中的节点，二叉搜索树找祖先就有点不一样了！| 235. 二叉搜索树的最近公共祖先，手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找，你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树，回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址，还得用回溯算法！| LeetCode：17.电话号码的字母组合，坑很多！来看看你掉过几次坑 | LeetCode：106.从中序与后序遍历序列构造二叉树，回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II，新学期要从学习二叉树开始！ | LeetCode：101. 对称二叉树https://www.bilibili.com/video/BV1fD4y117gp
思路：中序遍历，和在数组中找频率最高的数差不多。由于众数可能不止一个，所以当count>maxCount时，清除收集到的众数，再添加最新的元素。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {TreeNode pre;int maxCount = Integer.MIN_VALUE;int count = 0;ArrayList<Integer> result;public int[] findMode(TreeNode root) {result = new ArrayList<>();findModeByInOrder(root);int[] array = result.stream().mapToInt(Integer::intValue).toArray();return array;}public void findModeByInOrder(TreeNode root) {if (root == null) {return;}findModeByInOrder(root.left);if (pre == null) {count = 1;} else if (pre.val == root.val) {count++;} else {count = 1;}pre = root;if (count == maxCount) {result.add(root.val);} else if (count > maxCount) {result.clear();result.add(root.val);maxCount=count;}findModeByInOrder(root.right);}
}236. 二叉树的最近公共祖先
题目链接：. - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com， 这里刷题顺序，详细题解，应有尽有！, 视频播放量 55175、弹幕量 725、点赞数 1743、投硬币枚数 1285、收藏人数 393、转发人数 95, 视频作者 代码随想录, 作者简介 哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：二叉树的最近公共祖先，数据结构每日一代码题寻找P 和Q的最近公共祖先（自留，二叉树的最近公共祖先：看动画学做算法题，数据结构每日代码题：找到值为X的所有祖先（自留，寻找值为X的节点的所有祖先节点，D09 倍增算法 P3379【模板】最近公共祖先（LCA）——信息学奥赛算法，递归方法寻找二叉树任意的两个节点的最近公共祖先 含代码展示和思路讲解，23王道数据结构 150页13题 二叉树 寻找最近公共祖先，23王道数据结构 134页05题 求二叉树公共祖先代码，数据结构-求二叉树的宽度（层序遍历的改写｜分析+手写伪代码）https://www.bilibili.com/video/BV1jd4y1B7E2
思路： 回溯自底向上查找，先查找左右子树是否有要找的节点，如果有则返回节点，没有则返回null，根节点根据左右子树查找结果来确定返回值，如果都为null，则说明该树没有要查找的节点，如果都不为null，则说明该根节点就是最近公共父节点，如果一个为null，一个不为null，那么直接返回不为null的值。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root== p || root == q || root == null) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if (left == null && right == null) {return null;} else if (left == null && right != null) {return right;} else if (left != null && right == null) {return left;}return root;}
}
