算法训练营day21

一、二叉搜索树的最小绝对差

参考链接530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

利用二叉搜索树的性质 + 中序遍历 获取递增序列，还可以解决其他问题

1. 173. 二叉搜索树迭代器 - 力扣（LeetCode）

2. 530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

3. 230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

4. 501. 二叉搜索树中的众数 - 力扣（LeetCode）

5. 938. 二叉搜索树的范围和 - 力扣（LeetCode）

6. 653. 两数之和 IV - 输入二叉搜索树 - 力扣（LeetCode）

7. getMinimumDifference方法是解决问题的关键方法。它接受一个TreeNode类型的参数root，表示二叉树的根节点。首先，通过调用inOrderTransfer方法，按照中序遍历的顺序将二叉树的节点值存储到list中。

8. 然后，创建一个大小为list长度的整型数组a，将list中的元素赋值给数组a。接下来，使用一个变量min初始化为整型的最大值Integer.MAX_VALUE。然后，通过遍历数组a，计算相邻两个元素的差值，并将较小的差值更新到min中。

9. 最后，返回min作为结果。

class Solution {
    List<Integer> list=new ArrayList<>();
    public int getMinimumDifference(TreeNode root) {
        inOrderTransfer(root);
        int[] a=new int[list.size()];
        for(int i=0;i<a.length;i++){
            a[i]=list.get(i);
        }
        int min=Integer.MAX_VALUE;
        for(int i=0;i<a.length-1;i++){
            min=Math.min(min, a[i+1]-a[i]);
        }
        return min;
    }
    private void inOrderTransfer(TreeNode root){
        if(root==null)return ;
        inOrderTransfer(root.left);
        list.add(root.val);
        inOrderTransfer(root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

二、二叉搜索树中的众数

1. findMode方法：接受一个TreeNode类型的参数root，表示二叉树的根节点。在该方法中，首先对成员变量进行初始化。然后，调用findMode1方法进行中序遍历，寻找众数。接着，根据resList中的众数，创建一个整型数组res，并将其返回作为结果。

2. findMode1方法是一个递归方法，用于执行中序遍历操作。它接受一个TreeNode类型的参数root，表示当前子树的根节点。方法首先判断root是否为空，如果为空则直接返回。然后，递归调用findMode1方法，遍历左子树。

3. 在遍历过程中，首先获取当前节点的值rootValue。然后，通过与前一个节点的值进行比较，判断当前节点值出现的次数。如果当前节点与前一个节点的值不同，说明出现了一个新的值，将计数count重置为1；否则，计数count加1。

4. 接下来，根据计数count与最大计数maxCount的比较，更新众数的结果数组resList和最大计数maxCount。如果count大于maxCount，则清空resList并将当前节点值添加进去，并更新maxCount为count；如果count等于maxCount，则将当前节点值添加到resList中。最后，将当前节点作为前一个节点pre。

   最后，递归调用findMode1方法，遍历右子树。

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

三、二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 该题用于记忆，DFS
        //解释题解终止条件中第三种情况中b情况，root == p 或者 root = q 说明当前树找到了p或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; // 1.
        if(left == null) return right; // 3.
        if(right == null) return left; // 4.
        return root; // 2. if(left != null and right != null) 如果左右子树都不为空，返回root
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15