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

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

530题目链接

1.递归法——使用双指针。因为是二叉搜索树，所以中序遍历是递增的。所以最小值的产生肯定是前一个和后一个之间。

class Solution {
    // 前一个指针
    TreeNode pre = null;
    // 最小差值
    int minVal = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        getMinimum(root);
         return minVal;
    }

    public void getMinimum(TreeNode cur) {
         if (cur == null) return;

         getMinimum(cur.left);

         int abs = 0;
         if (pre != null && (abs = Math.abs(cur.val - pre.val)) < minVal) {
             minVal = abs;
         }
         pre = cur;

         getMinimum(cur.right);
    }
}

2.迭代法

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        TreeNode cur = root;
        int minVal = Integer.MAX_VALUE;
        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                int abs = 0;
                if (pre != null && (abs = Math.abs(pre.val-cur.val)) < minVal) {
                    minVal = abs;
                }
                pre = cur;
                cur = cur.right;
            }
        }
        return minVal;
    }
}

501.二叉搜索树中的众数

501题目链接

1.递归法——双指针

class Solution {
    // 最大频率
    int maxCount = 0;
    // 当前连续次数
    int count = 0;
    // 上一个节点指针
    TreeNode pre = null;

    public int[] findMode(TreeNode root) {
        if (root == null ) return null;
        if (root.left == null && root.right == null) return new int[]{root.val};
        List<Integer> list = new LinkedList<>();
        findMode(root, list);
        return list.stream().mapToInt(i -> i).toArray();
    }

    public void findMode(TreeNode cur, List<Integer> list) {
        if (cur == null) return;

        // 左
        findMode(cur.left, list);

        // 中
        if (pre == null) count = 1;
        else if (pre.val == cur.val) count++;
        else count=1;

        if (count == maxCount) {
            list.add(cur.val);
        } else if (count > maxCount) {
            maxCount = count;
            list.clear();
            list.add(cur.val);
        }
        pre = cur;

        // 右
        findMode(cur.right, list);
    } 
}

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

236题目链接

1.看了视频在写的

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

        return root;
    }
}

参考资料

代码随想录