代码随想录算法训练营第21天

今日任务

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

链接：https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X (opens in a new tab)

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

自己想法

搜索树的最小差一定在中序遍历相邻两节点间产生，而且只需后比前即可，因此用一个pre记录前一个节点，然后中序遍历时比较即可。

class Solution {
    public int min;
    public TreeNode pre;
    public int getMinimumDifference(TreeNode root) {
        this.min = -1;
        this.pre = null;
        invert(root);
        return this.min;
    }
    // 1.返回：无
    public void invert(TreeNode node) {
        // 2.空节点结束
        if(node == null) return;
        // 3.递归逻辑
        // 左：
        invert(node.left);
        // 中：如果有上一个元素，那就比一比
        if(this.pre != null) {
            int now_diff = node.val - this.pre.val;
            if(this.min != -1) this.min = Math.min(this.min, now_diff);
            else this.min = now_diff;
        }
        this.pre = node;
        // 右：
        invert(node.right);
    }
}

501.二叉搜索树中的众数

自己想法

搜索树的众数一定在中序遍历连续，因此用一个pre记录前一个节点，看一不一样。同时记录当前元素出现频次以及最大频次，如果相等就加入结果集，如果大于就清空结果集，如果小于就不管。

class Solution {
    public TreeNode pre = null;
    public int freq = 1;
    public int max_freq = 1;
    public List<Integer> ans;
    public int[] findMode(TreeNode root) {
        this.ans = new ArrayList<>();
        invert(root);
        return ans.stream().mapToInt(i -> i).toArray();
    }
    public void invert(TreeNode node) {
        if(node == null) return;
        // 左：
        invert(node.left);
        // 中：
        // 有前一个节点（说明不是第一个节点）
        if(this.pre != null) {
            // 和前一个节点值相等，频次加一
            if(node.val == this.pre.val) {
                this.freq ++;
                // 如果频次和最大频次相等，加入结果集
                if(this.freq == this.max_freq) {
                    this.ans.add(node.val);
                }
                // 如果频次大于最大频次，清空结果集，加入当前节点值，更新最大频次
                else if(this.freq > this.max_freq) {
                    this.ans.clear();
                    this.ans.add(node.val);
                    this.max_freq = this.freq;
                }
            }
            // 和前一个节点值不相等，频次重置为1
            else {
                this.freq = 1; // 频次重置为1
                // 确保不漏频次都为1的的情况
                if(this.freq == this.max_freq) this.ans.add(node.val);
            }
        }
        // 没有前一个节点，说明是第一个节点，直接加入结果集
        else {
            this.ans.add(node.val);
        }
        // 更新前一个节点
        this.pre = node;
        // 右：
        invert(node.right);
    }
}

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

自己想法（推荐看完自己的，再去看一眼题解）

后序遍历（左右中），是天然的回溯过程，用返回值表示当前节点是不是p或q的父母。也就是在回溯时告诉自己的父母，自己是不是p或q的父母。

class Solution {
    public boolean hasFound = false;
    public TreeNode ans = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        invert(root, p, q);
        return this.ans;
    }
    // 返回值[]表示当前节点是不是p或q的父母，都是则为[1, 1],反之为[0, 0],只有一个则为[1, 0]或[0, 1]
    public int[] invert(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return new int[]{0, 0};
        int[] left_check = invert(root.left, p, q);
        int[] right_check = invert(root.right, p, q);
        int p_check = 0;
        if(root == p) p_check = 1;
        int q_check = 0;
        if(root == q) q_check = 1;
        if(!hasFound) {
            if(left_check[0] == 1 && left_check[1] == 1) { // 答案恰好在左child手里
                this.hasFound = true;
                this.ans = root.left;
                return new int[]{1, 1};
            }
            else if(right_check[0] == 1 && right_check[1] == 1) { // 答案恰好在右child手里
                this.hasFound = true;
                this.ans = root.right;
                return new int[]{1, 1};
            }
            else if((left_check[0] + left_check[1] + right_check[0] + right_check[1]) == 2) { // 自己在中间收渔翁之利
                this.hasFound = true;
                this.ans = root;
                return new int[]{1, 1};
            }
            else { // 在中间努力一下
                if((left_check[0] + left_check[1] + p_check + right_check[0] + right_check[1] + q_check) == 2) {
                    // 努力成功
                    this.hasFound = true;
                    this.ans = root;
                    return new int[]{1, 1};
                }
                else {
                    // 努力失败，寄希望于parent
                    return new int[]{left_check[0] + left_check[1] + p_check, right_check[0] + right_check[1] + q_check};
                }
            }
        }
        else return new int[]{1, 1};
    }
}

题解想法

思路差不多，但是精简版：直接用递归函数返回值来回传结果。当发现当前节点就是p或q时，不必再往下递归，直接返回当前节点，去另一边找另一个p或q即可，找不到就说明另一个p或q就在当前节点的子树中。也算是剪枝吧。

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return invert(root, p, q);
    }
    public TreeNode invert(TreeNode root, TreeNode p, TreeNode q) {
        if(root == p || root == q || root == null) return root;
        TreeNode left = invert(root.left, p, q);
        TreeNode right = invert(root.right, p, q);
        if(left != null && right == null) return left;
        else if(left == null && right != null) return right;
        else if(left != null && right != null) return root;
        else return null;
    }
}