随想录日记part17

$time：$ 2024.03.12

---

---

主要内容：今天的主要内容是二叉树的第六部分，主要涉及二叉搜索树的最小绝对差
；二叉搜索树中的众数；二叉树的最近公共祖先。

• 530.二叉搜索树的最小绝对差
• 501.二叉搜索树中的众数
• 236. 二叉树的最近公共祖先

---

---

Topic1二叉搜索树的最小绝对差

题目：

给你一个二叉搜索树的根节点 $root$ ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例：

输入： $root=[4,2,6,1,3]$
输出： $1$

思路：

把二叉搜索树转换成有序数组，然后遍历一遍数组，就统计出来最小差值:direct/b54a915741f74f9ab515b28243d24f40.gif)

总体代码如下：

class Solution {
    int result = Integer.MAX_VALUE;
    TreeNode pre;// 记录上个节点

    public int getMinimumDifference(TreeNode root) {
        if (root == null)
            return 0;
        center_search(root);
        return result;
    }

    private void center_search(TreeNode root) {// 中序遍历
        if (root == null)
            return;
        // 左
        center_search(root.left);
        // 中
        if (pre != null)
            result = Math.min(result, root.val - pre.val);
        pre = root;
        // 右
        center_search(root.right);
    }
}

---

---

Topic2二叉搜索树中的众数

题目：

给你一个含重复值的二叉搜索树 $BST$ 的根节点 $root$ ，找出并返回 $BST$ 中的所有众数（即出现频率最高的元素）。
如果树中有不止一个众数，可以按任意顺序返回。
假定 BST 满足如下定义：

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

输入： $root=[1,null,2,2]]$
输出： $[2]$

思路：

既然是搜索树，它中序遍历就是有序的。
如图：

总体代码如下： 递归法：

class Solution {
    // 定义一些辅助数据
    ArrayList<Integer> resList;
    int maxCount;
    int count;
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        check(root);
        int[] nums = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            nums[i] = resList.get(i);
        }
        return nums;
    }

    private void check(TreeNode root) {
        if (root == null)
            return;
        // 左
        check(root.left);
        // 中
        if (pre == null || root.val != pre.val) {
            count = 1;
        } else {
            count++;
        }
        if (count > maxCount) {
            resList.clear();
            resList.add(root.val);
            maxCount = count;
        } else if (count == maxCount) {
            resList.add(root.val);
        }
        pre = root;
        check(root.right);
    }
}

---

---

Topic3二叉树的最近公共祖先

题目：

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

示例：

输入： $root=[3,5,1,6,2,0,8,null,null,7,4],p=5,q=1$
输出： $3$

思路：

后序遍历递归法：

代码如下：

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 root;
        if (left != null && right == null)
            return left;
        else if (left == null && right != null)
            return right;
        else
            return null;
    }
}