代码随想录算法训练营第21天（二叉树7 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ● 236. 二叉树的最近公共祖先

时间：2025-03-29 07:55:35

二叉树part07

  • 530.二叉搜索树的最小绝对差
    • 解题思路
  • 501.二叉搜索树中的众数
    • 解题思路
    • 解题步骤
  • 236. 二叉树的最近公共祖先 （理解不透彻，需复习
    • 解题思路

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

需要领悟一下二叉树遍历上双指针操作，优先掌握递归
题目链接/文章讲解：530.二叉搜索树的最小绝对差
视频讲解：530.二叉搜索树的最小绝对差

解题思路

二叉搜索树，考虑用中序遍历
遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值
要学会在递归遍历的过程中如何记录前后两个指针
明确递归函数需不需要返回值
该题涉及到回溯

// 递归 前后指针
class Solution {
    TreeNode pre;  // 记录上一个遍历的节点
    int ans = Integer.MAX_VALUE;;
    public int getMinimumDifference(TreeNode root) {
        if(root == null)return 0;
        dfs(root);
        return ans;
    }
    public void dfs(TreeNode root){
        if(root == null) return;
        // 左
        dfs(root.left);
        // 中
        if(pre != null){
            ans = Math.min(ans, root.val - pre.val);
            pre = root;
        }
        pre = root;
        // 右
        dfs(root.right);
    }
}

501.二叉搜索树中的众数

和 530差不多双指针思路，不过 这里涉及到一个很巧妙的代码技巧。
可以先自己做做看，然后看我的视频讲解。
题目链接/文章讲解：501.二叉搜索树中的众数
视频讲解：501.二叉搜索树中的众数

解题思路

  1. 将二叉搜索树看作一颗普通的树
    最直观的方法是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。
  2. 运用二叉搜索树的特点
    应该是先遍历一遍二叉树，找出最大频率（maxCount），然后再重新遍历一遍二叉树把出现频率为maxCount的元素放进集合。（因为众数有多个）
    运用了一个统计最高出现频率元素集合的技巧， 要不然就要遍历两次二叉搜索树才能把这个最高出现频率元素的集合求出来。
    为什么没有这个技巧一定要遍历两次呢？ 因为要求的是集合，会有多个众数，如果规定只有一个众数，那么就遍历一次稳稳的了。
    我们可以顺序扫描中序遍历序列，用 rootValue 记录当前的数字，用 count 记录当前数字重复的次数，用 maxCount 来维护已经扫描过的数当中出现最多的那个数字的出现次数，用 resList记录出现的众数。每次扫描到一个新的元素：

解题步骤

  1. 首先更新 rootValue 和 count:
  • 如果该元素和 rootValue 相等，那么 count自增 1；
  • 否则将 rootValue 更新为当前数字，count复位为 1。
  1. 然后更新 maxCount：
  • 如果 count=maxCount，那么说明当前的这个数字 rootValue 出现的次数等于当前众数出现的次数，将 rootValue 加入resList中；
  • 如果 count>maxCount，那么说明当前的这个数字 rootValue 出现的次数大于当前众数出现的次数，因此，我们需要将 maxCount 更新为 count，清空resList后将 rootValue 加入 resList。
// 利用二叉搜索树的特性 和记录众数的一个技巧 一次遍历解决
class Solution {
    ArrayList<Integer> resList;
    int maxCount;
    int count;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        findMode1(root);
        int[] res = new int[resList.size()];
        for(int i = 0; i < resList.size(); i++){
            res[i] = resList.get(i);
        }
        return res;
    }
    public void findMode1(TreeNode root){
        if(root == null) return;
        // 左
        findMode1(root.left);
        // 中
        int rootValue = root.val;
        // 计数
        if(pre == null || rootValue != pre.val){
            count = 1;
        }else{
            count++;
        }
        // 更新结果以及maxCount
        if(count > maxCount){
            resList.clear();
            resList.add(rootValue);
            maxCount = count;
        }else if(count == maxCount){
            resList.add(rootValue);
        }
        pre =root;
        // 右
        findMode1(root.right);
    }
}

public class Solution {
    private void searchBST(TreeNode cur, Map<Integer, Integer> map) {
        if (cur == null) return;
        
        map.put(cur.val, map.getOrDefault(cur.val, 0) + 1);  // 中     
        searchBST(cur.left, map);  // 左
        searchBST(cur.right, map); // 右
    }

    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> modes = new ArrayList<>();

        searchBST(root, map);

        int maxFrequency = 0;

        for (int frequency : map.values()) {
            maxFrequency = Math.max(maxFrequency, frequency);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == maxFrequency) {
                modes.add(entry.getKey());
            }
        }
        int[] result = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            result[i] = modes.get(i);
        }
        return result;
    }
}

236. 二叉树的最近公共祖先 （理解不透彻，需复习

本题其实是比较难的，可以先看我的视频讲解
题目链接/文章讲解：236. 二叉树的最近公共祖先
视频讲解：236. 二叉树的最近公共祖先

解题思路

  1. 遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。那么二叉树如何可以自底向上查找呢？回溯啊，二叉树回溯的过程就是从低到上。后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。
    2.情况讨论
  • p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
  • p=roo ，且 q 在 root 的左或右子树中；
  • q=root ，且 p 在 root 的左或右子树中；
  1. 本题函数有返回值，是因为回溯的过程需要递归函数的返回值做判断（虽然是要遍历整棵树而不是某个路径）
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) return null;  //p和q都未找到
        else if(left == null && right != null) return right; //只找到一个
        else if(left != null && right == null) return left;  //只找到一个
        else return root; // p和q都找到
    }
}

// 简洁版代码
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) return right;
        if(right == null) return left;
        return root;
    }
}

相关文章