CC's Boat

一顾青山舟远去，归来仍是顾青山

0%

代码随想录算法训练营第二十一天

Posted on

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

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
class Solution {
    TreeNode prev = null;
    int minGap = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        getMD(root);
        return minGap;
    }


    public void getMD (TreeNode root) {
        
        if (root == null) {
            return;
        }

        // left
        getMD(root.left);

        // root
        if (prev != null) {

            // actually, no need to use abs, as this is a BST, 
            // the value of the node behind should be larger than its former element
            // int gap = Math.abs(root.val - prev.val);
            // int gap = root.val - prev.val;
            // if (gap < minGap) {
            //     minGap = gap;;
            // }

            minGap = Math.min(minGap, root.val - prev.val);
        }
        prev = root;

        // right
        getMD(root.right);
    }
}

事实上二叉搜索树中序遍历就是一个单调不减的数组, 想清楚这一点就好解决了，双指针操作，寻找有序数组最大差值。

LeetCode 501.二叉搜索树中的众数

如果这是一颗普通二叉树，那么它的中序遍历就无法被视为一个单调序列，那么就无法使用双指针法解决了，就得老老实实地使用任何一种方式遍历二叉树，统计各个元素出现的次数，用map存储，然后按照map的value进行排序，取出现频次最高的元素，比较麻烦。 但好在我们的目标是二叉搜索树。

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
46
47
class Solution {

    // 1 1 2 2 2 2 3 4 5 6 7 8 9 9 9 9 9
    private TreeNode prev;
    private int highestFrequence = 0;
    private int tempCount = 0;
    private List<Integer> ans = new LinkedList();
    
    public int[] findMode(TreeNode root) {
        inorder(root);
        int[] modes = ans.stream().mapToInt(i->i).toArray();
        return modes;
    }

    private void inorder(TreeNode cur) {

        if (cur == null) {
            return;
        }

        inorder(cur.left);

        // Step 1: update the tempCount
        if (prev == null) {
            tempCount = 1;
        }else if (prev.val == cur.val){
            tempCount++;
        }else {
            tempCount = 1;
        }

        // Step 2: update the ans list if necessary
        if (tempCount == highestFrequence) {
            ans.add(cur.val);
        }else if (tempCount > highestFrequence) {
          	// note here, if higher frequence exists, then drop all the current cached res
            highestFrequence = tempCount;
            ans.clear();
            ans.add(cur.val);
        }

        // Step 3: update the prev pointer
        prev = cur;

        inorder(cur.right);
    }
}

LeetCode 235.二叉树的最近公共祖先

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
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if(root == null || root.val == p.val || root.val == q.val){
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // as a root node of any sub-tree, is my left branch and my right branck both 
        // do not contain the target nodes, then I would definitely not be the LCA
        if(left == null && right == null) {
            return null;
            // similarly, if both my sub-tree contain the target, then because we
            // are backtracking, myself must be the LCA
        }else if (left != null && right != null) {
            return root;

            // if left does not contain target nodes, then the ans must be in the rightside
        }else if (left == null && right != null) {
            return right;
        }else {
            // the same with the leftside
            return left;
        }
    }
}