代码随想录算法训练营第二十一天 |530.二叉搜索树的最小绝对差，501.二叉搜索树中的众数，236.二叉树的最近公共祖先（待补充）

傷城~ 2024-04-23 04:07 39阅读 0赞

### 530.二叉搜索树的最小绝对差 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ -]

2、文章讲解：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 1]

3、题目：

给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。

示例：

![cad47fcaf000a73e81ae8f27b225dfd3.png][]

提示：树中至少有 2 个节点。

4、视频链接：

[又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树\_哔哩哔哩\_bilibili][LeetCode_654._bilibili]

5、思路：

class Solution {
        TreeNode pre;// 记录上一个遍历的结点
        int result = Integer.MAX_VALUE;
        public int getMinimumDifference(TreeNode root) {
           if(root==null)return 0;
           traversal(root);
           return result;
        }
        public void traversal(TreeNode root){
            if(root==null)return;
            //左
            traversal(root.left);
            //中
            if(pre!=null){
                result = Math.min(result,root.val-pre.val);
            }
            pre = root;
            //右
            traversal(root.right);
        }
    }

class Solution {
        public int getMinimumDifference(TreeNode root) {
            Stack<TreeNode> stack = new Stack<>();
            TreeNode pre = null;
            int result = Integer.MAX_VALUE;
    
            if(root != null)
                stack.add(root);
            while(!stack.isEmpty()){
                TreeNode curr = stack.peek();
                if(curr != null){
                    stack.pop();
                    if(curr.right != null)
                        stack.add(curr.right);
                    stack.add(curr);
                    stack.add(null);
                    if(curr.left != null)
                        stack.add(curr.left);
                }else{
                    stack.pop();
                    TreeNode temp = stack.pop();
                    if(pre != null)
                        result = Math.min(result, temp.val - pre.val);
                    pre = temp;
                }
            }
            return result;
        }
    }

### 501.二叉搜索树中的众数 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 2]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

*  结点左子树中所含结点的值小于等于当前结点的值
 *  结点右子树中所含结点的值大于等于当前结点的值
 *  左子树和右子树都是二叉搜索树

例如：

给定 BST \[1,null,2,2\],

![e2c03bce048ff92b6dc2b1584b990847.png][]

返回\[2\].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

4、视频链接：

[不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数\_哔哩哔哩\_bilibili][_ LeetCode_501._bilibili]

5、思路：

class Solution {
        public int[] findMode(TreeNode root) {
            int count = 0;
            int maxCount = 0;
            TreeNode pre = null;
            LinkedList<Integer> res = new LinkedList<>();
            Stack<TreeNode> stack = new Stack<>();
    
            if(root != null)
                stack.add(root);
            
            while(!stack.isEmpty()){
                TreeNode curr = stack.peek();
                if(curr != null){
                    stack.pop();
                    if(curr.right != null)
                        stack.add(curr.right);
                    stack.add(curr);
                    stack.add(null);
                    if(curr.left != null)
                        stack.add(curr.left);
                }else{
                    stack.pop();
                    TreeNode temp = stack.pop();
                    if(pre == null)
                        count = 1;
                    else if(pre != null && pre.val == temp.val)
                        count++;
                    else
                        count = 1;
                    pre = temp;
                    if(count == maxCount)
                        res.add(temp.val);
                    if(count > maxCount){
                        maxCount = count;
                        res.clear();
                        res.add(temp.val);
                    }
                }
            }
            int[] result = new int[res.size()];
            int i = 0;
            for (int x : res){
                result[i] = x;
                i++;
            }
            return result;    
        }
    }

### 236.二叉树的最近公共祖先 ###

1、题目链接：[力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台][LeetCode_ - 3]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = \[3,5,1,6,2,0,8,null,null,7,4\]

![d2210a6055dad904f1378922119bc891.png][]

示例 1: 输入: root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2: 输入: root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 4 输出: 5 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

*  所有节点的值都是唯一的。
 *  p、q 为不同节点且均存在于给定的二叉树中。

4、思路：

class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) { // 递归结束条件
                return root;
            }
    
            // 后序遍历
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
    
            if(left == null && right == null) { // 若未找到节点 p 或 q
                return null;
            }else if(left == null && right != null) { // 若找到一个节点
                return right;
            }else if(left != null && right == null) { // 若找到一个节点
                return left;
            }else { // 若找到两个节点
                return root;
            }
        }
    }

###  ###

[LeetCode_ -]: https://leetcode.cn/problems/maximum-binary-tree/
[LeetCode_ - 1]: https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
[cad47fcaf000a73e81ae8f27b225dfd3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/9fd7511cdb8648df8b82f16b27cc46b3.png
[LeetCode_654._bilibili]: https://www.bilibili.com/video/BV1MG411G7ox
[LeetCode_ - 2]: https://leetcode.cn/problems/find-mode-in-binary-search-tree/
[Link 1]: https://www.programmercarl.com/0501.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E4%BC%97%E6%95%B0.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[e2c03bce048ff92b6dc2b1584b990847.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/8daf8983a56941168c15e850e9bfc8f3.png
[_ LeetCode_501._bilibili]: https://www.bilibili.com/video/BV1fD4y117gp
[LeetCode_ - 3]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
[Link 2]: https://www.programmercarl.com/0236.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[d2210a6055dad904f1378922119bc891.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e2b9bad3ea76438b9c92d3bc2e61567e.png