代码随想录算法训练营第二十天 | 二叉搜索树的最小绝对差、二叉搜索树中的众数、二叉树的最近公共祖先

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

leetcode
文档题解
视频题解

因为是个二叉搜索树，所以是有序的序列，有序序列中相邻值的差才有可能最小，所以找相邻值的最小差值即可。类似于验证二叉搜索树，使用 prev 记录前一个节点，与当前节点做减法，并更新更小的差值。

// 递归法
class Solution {
    // 记录最小值
    private int min = Integer.MAX_VALUE;
    // 记录上一个节点
    private TreeNode prev = null;

    public int getMinimumDifference(TreeNode root) {
        traversal(root);
        return min;
    }

    public void traversal(TreeNode root) {
        if (root == null) return;
        traversal(root.left);
        // 如果 prev 不为空，则求差，并更新最小差值
        if (prev != null) {
            int x = root.val - prev.val;
            if (x < min) {
                min = x;
            }
        }
        // 更新 prev 为 root，然后递归右子树
        prev = root;
        traversal(root.right);
    }
}

// 迭代法 - 中序遍历的模板
class Solution {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        // 当前遍历的节点
        TreeNode curr = root;
        // 上一个遍历的节点
        TreeNode prev = null;

        int min = Integer.MAX_VALUE;

        while (curr != null || !st.isEmpty()) {
            if (curr != null) {
                // 只要当前节点不为空，就往栈中存储当前节点，然后一直往左子树深入
                st.push(curr);
                curr = curr.left;
            } else {
                // 出栈的就是中间节点
                curr = st.pop();
                // 处理
                if (prev != null) {
                    int x = curr.val - prev.val;
                    if (x < min) {
                        min = x;
                    }
                }
                // 更新 prev
                prev = curr;
                // 开始遍历右子树
                curr = curr.right;
            }
        }
        return min;
    }
}

501. 二叉搜索树中的众数

leetcode
文档题解
视频题解

最直观的做法，使用 map 存储频率，是不是二叉搜索树无所谓，可以使用任意遍历顺序。

// 迭代法 - 借用额外的空间存储频率
class Solution {
    public int[] findMode(TreeNode root) {
        // 存储每个值出现的频率
        Map<Integer, Integer> map = new HashMap<>();
        Stack<TreeNode> st = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !st.isEmpty()) {
            if (curr != null) {
                st.push(curr);
                curr = curr.left;
            } else {
                curr = st.pop();
                map.put(curr.val, map.getOrDefault(curr.val, 0) + 1);
                curr = curr.right;
            }
        }

        // 先遍历一遍 map，找到最大频率
        int max = Integer.MIN_VALUE;
        for (int val: map.values()) {
            if (val > max) {
                max = val;
            }
        }

        // 再遍历一遍 map，收集最大频率的节点
        List<Integer> list = new LinkedList<>();
        for (Map.Entry<Integer, Integer> e: map.entrySet()) {
            if (e.getValue() == max) {
                list.add(e.getKey());
            }
        }

        // list 转 array，输出
        int[] res = new int[list.size()];
        int i = 0;
        for (int e: list) {
            res[i++] = e;
        }
        return res;
    }
}

因为是二叉搜索树，所以是有序的，相同元素是相邻的，那么统计频率就可以使用双指针的方法，一前一后。

// 递归法
class Solution {
    private int maxCount;
    private int count;
    private TreeNode prev;
    private List<Integer> list;
    public int[] findMode(TreeNode root) {
        maxCount = Integer.MIN_VALUE;
        count = 0;
        prev = null;
        list = new LinkedList<>();
        traversal(root);
        int[] res = new int[list.size()];
        int i = 0;
        for (int e: list) {
            res[i++] = e;
        }
        return res;
    }
    public void traversal(TreeNode root) {
        if (root == null) return;
        traversal(root.left);

        if (prev == null) {
            // 第一个节点，频率记为 1
            count = 1;
        } else if (prev.val == root.val) {
            // 重复的节点，频率 +1
            count++;
        } else {
            // 新节点，频率重置为 1
            count = 1;
        }

        // 和当前最大频率相等，放进预结果列表
        if (count == maxCount) {
            list.add(root.val);
        }

        // 频率更大，更新 maxCount，
        // 之前的预结果列表作废，因为有了频率更大的，并将最新的大频率值放进预结果列表
        if (count > maxCount) {
            maxCount = count;
            list.clear();
            list.add(root.val);
        }

        prev = root;

        traversal(root.right);
    }
}

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

leetcode
文档题解
视频题解

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (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;
        if (left != null && right != null) return root;

        return left != null ? left : right;
    }
}