[toc]

TREE

Binary trees can be classified based on their structure and properties. Here are the main classifications of binary trees:

Based on Node Relationships

  1. Full Binary Tree:

    • Every node has either 0 or 2 children.
    • Also known as a strictly binary tree.

  2. Complete Binary Tree:

    • All levels are completely filled except possibly for the last level.

    • The last level has all nodes as left as possible.

      img

  3. Perfect Binary Tree:

    • All internal nodes have two children, and all leaf nodes are at the same level.

  4. Balanced Binary Tree:

    • The height of the left and right subtrees of any node differ by at most one.

  5. Degenerate (or Pathological) Tree:

    • Each parent node has only one child. This degenerates the tree into a linked list.

Based on Specific Properties

  1. Binary Search Tree (BST):
    • For each node, all elements in the left subtree are less than the node, and all elements in the right subtree are greater.
  2. AVL Tree:
    • A self-balancing binary search tree where the difference in heights between the left and right subtrees cannot be more than one for all nodes.
  3. Red-Black Tree:
    • A self-balancing binary search tree with an extra bit of storage per node (the color), which helps balance the tree during insertions and deletions.
  4. Splay Tree:
    • A self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again.

Special Types

  1. Threaded Binary Tree:
    • A binary tree where pointers that would normally be null are used to point to the in-order predecessor or successor.
  2. Heaps:
    • Max-Heap: A complete binary tree where the value of each node is greater than or equal to the values of its children.
    • Min-Heap: A complete binary tree where the value of each node is less than or equal to the values of its children.

Application-Specific Trees

  1. Expression Tree:
    • A tree used to represent expressions, where the leaves are operands and internal nodes are operators.
  2. Decision Tree:
    • A tree used in decision analysis, where nodes represent decisions or outcomes.

Traversal-Based Classification

  1. Binary Tree Traversal Types
    • In-Order Traversal: Left, Root, Right
    • Pre-Order Traversal: Root, Left, Right
    • Post-Order Traversal: Left, Right, Root
    • Level-Order Traversal: Level by level from root to leaves
1
2
3
4
5
6
7
8
9
10
11
12
13
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

in-order pre-order post-order traversal

Recursion

  1. Determine the parameters and return value of the recursive function: Since we need to collect the values of the nodes in pre-order traversal, we need to pass a list to store the node values. We don’t need to process any other data or return a value, so the return type of the recursive function is void. The code is as follows:
1
void preOrderTraversal(TreeNode cur, List<Integer> list)
  1. Determine the termination condition: During recursion, we need to know when to end the recursion. This is when the current node being traversed is null. Therefore, if the current node is null, we simply return. The code is as follows:
1
2

if (cur == null) return;
  1. Determine the logic for a single layer of recursion: Pre-order traversal follows the order: root, left, right. In a single layer of recursion, we first process the root node’s value, then traverse the left subtree, and finally the right subtree. The code is as follows:
1
2
3
list.add(cur.val);       // Root
preOrderTraversal(cur.left, list);  // Left
preOrderTraversal(cur.right, list); // Right

144.Binary Tree Preorder Traversal

Easy

Given the root of a binary tree, return the preorder traversal of its nodes’ values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();
    public List<Integer> preorderTraversal(TreeNode root) {
        preorder(root);
        return res;
    }
    public void preorder ( TreeNode root ){
        if(root == null) return ;
        res.add(root.val);
        /*
        if(root.left != null){
            preorder(root.left);
        }
        if(root.right != null){
            preorder(root.right);
        }
        here, the if statement is unecessary!!!
        */
        preorder(root.left);
        preorder(root.right);
    }
}

94. Binary Tree Inorder Traversal

Easy

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();
    public List<Integer> inorderTraversal(TreeNode root) {
        inorder(root);
        return res;
    }
    public void inorder ( TreeNode root ){
        if(root == null) return ;
        
        inorder(root.left);
        res.add(root.val);
        inorder(root.right);
        
    }
}

145. Binary Tree Postorder Traversal

Easy

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    ArrayList<Integer> res = new ArrayList<Integer>();
    public List<Integer> postorderTraversal(TreeNode root) {
        postorder(root);
        return res;
    }
    public void postorder ( TreeNode root ){
        if(root == null) return ;
        
        postorder(root.left);
        postorder(root.right);
        res.add(root.val);
        
    }
}

iterative method

STACK

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left; //一路向西
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

level order traversal

226 and 101, using recursion is more efficient, but level order traversal can also solve the problem

226. Invert Binary Tree （recursion)

Easy

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

img

1
2
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// recursion
class Solution {
    public TreeNode invertTree(TreeNode root) {
        invert(root);
        return root;
    }
    public void invert(TreeNode root){
        if(root == null) return;
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invert(root.left);
        invert(root.right);
    }
}

101. Symmetric Tree （recursion)

😍Easy

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

img

1
2
Input: root = [1,2,2,3,4,4,3]
Output: true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return sym(root.left, root.right);
    }
    public boolean sym(TreeNode one, TreeNode two){
        if(one == null && two == null) return true;
        if(one == null && two != null || one != null && two == null) return false;
        //if(one.val == two.val ) return true; !!!!!!!! if it returns true here, then it wont go and check the deeper
        if(one.val != two.val ) return false;
        boolean comp1 = sym(one.left, two.right);
        boolean comp2 =sym(one.right, two.left);
        //return comp1 || comp2; !!!!!!!!! not OR
        return comp1 && comp2;
    }
}

|| &&

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
public class LogicalAndExample {
    public static void main(String[] args) {
        boolean a = true;
        boolean b = true;
        boolean c = false;
        
        // Case 1: Both true
        boolean result1 = a && b; // true && true = true
        System.out.println("a && b: " + result1); // Output: true
        
        // Case 2: One false
        boolean result2 = a && c; // true && false = false
        System.out.println("a && c: " + result2); // Output: false
        
        // Case 3: Both false
        boolean result3 = c && c; // false && false = false
        System.out.println("c && c: " + result3); // Output: false
    }
}

public class LogicalOrExample {
    public static void main(String[] args) {
        boolean a = true;
        boolean b = true;
        boolean c = false;
        
        // Case 1: Both true
        boolean result1 = a || b; // true || true = true
        System.out.println("a || b: " + result1); // Output: true
        
        // Case 2: One true, one false
        boolean result2 = a || c; // true || false = true
        System.out.println("a || c: " + result2); // Output: true
        
        // Case 3: Both false
        boolean result3 = c || c; // false || false = false
        System.out.println("c || c: " + result3); // Output: false
    }
}

when to use recursion in tree problems:

Traversal: Recursion is commonly used for tree traversal, such as in-order, pre-order, and post-order traversals. These traversal methods involve visiting each node of the tree in a specific order.

Transformation: Recursion can be used to transform or modify the tree in some way. This can include tasks like inverting a binary tree, as shown in the first example, or flattening a tree structure.

Validation and Comparison: Recursion is often used to validate the structure or properties of a tree, such as checking if a binary tree is symmetric, as shown in the second example. Recursive algorithms can compare subtrees and validate whether certain conditions hold true.

Searching and Path Finding: Recursive algorithms can be employed to search for nodes in a tree or find paths within the tree, such as finding the shortest path between two nodes or finding the common ancestor of two nodes.

Backtracking: In certain scenarios, backtracking is needed, especially in problems where you need to explore different paths or combinations within the tree. Recursion is well-suited for backtracking algorithms.

Divide and Conquer: Recursive divide-and-conquer algorithms are frequently used in tree problems where you break down the problem into smaller subproblems, solve each subproblem recursively, and then combine the results.

here are some examples of tree problems where recursion is commonly used:

  1. Binary Tree Traversals: Problems requiring in-order, pre-order, or post-order traversals of a binary tree. For example, printing the nodes of a binary tree in in-order traversal.
  2. Depth-First Search (DFS): DFS on a tree is inherently recursive. Problems involving exploring all possible paths from the root to leaves, or finding a specific node, often use recursion. For instance, checking if a path exists from the root to a given leaf node.
  3. Binary Tree Modification: Tasks like inverting a binary tree or converting a binary search tree into a sorted doubly linked list can be efficiently solved using recursion.
  4. Binary Search Trees (BSTs): Many operations on BSTs, such as insertion, deletion, and searching, can be implemented recursively.
  5. Symmetric Trees and Identical Trees: Problems checking if a tree is symmetric around its center or if two trees are identical often use recursive algorithms to compare corresponding nodes.
  6. Lowest Common Ancestor (LCA): Finding the lowest common ancestor of two nodes in a binary tree can be solved using recursion by traversing the tree and tracking the paths to the nodes.
  7. Maximum/Minimum Depth of Binary Tree: Calculating the maximum or minimum depth of a binary tree involves traversing the tree recursively and tracking the depth of each node.
  8. Validate Binary Search Tree (BST): Verifying whether a binary tree is a valid BST typically involves a recursive approach to check if each node satisfies the BST property.

Binary tree level order traversal

102. Binary Tree Level Order Traversal

Medium

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Example 1:

img

1
2
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int num = que.size(); 
            // the number of nodes this level has
            List<Integer> row  = new ArrayList<>(); 
            // to store the value of the nodes on the same row
            while(num > 0){
                TreeNode temp = que.poll();
                row.add(temp.val);
                if(temp.left != null) que.add(temp.left);
                if(temp.right != null) que.add(temp.right);
                num--;
            }
            res.add(row);
        }
        return res;
    }
}

Recursion method

104. Maximum Depth of Binary Tree

😭😍Easy

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

img

1
2
Input: root = [3,9,20,null,null,15,7]
Output: 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// first try: (Recursion)

class Solution {
    public int maxDepth(TreeNode root) {
        return dep(root);
    }

    public int dep(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(dep(root.left) + 1, dep(root.right) + 1);
    }
}


  • ```c++
    // post order traversal
    class Solution {
    public:
    int getdepth(TreeNode* node) {
    if (node == NULL) return 0;
    int leftdepth = getdepth(node->left); // 左
    int rightdepth = getdepth(node->right); // 右
    int depth = 1 + max(leftdepth, rightdepth); // 中
    return depth;
    }
    int maxDepth(TreeNode* root) {
    return getdepth(root);
    }
    };
    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

    * [height vs. depth](https://www.geeksforgeeks.org/height-and-depth-of-a-node-in-a-binary-tree/)

    **The depth of a node is the number of edges from the root to the node.** 

    **The height of a node is the number of edges from the node to the deepest leaf**

    ## [111. Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/)

    [solution](https://programmercarl.com/0111.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%9C%80%E5%B0%8F%E6%B7%B1%E5%BA%A6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE)

    😭Easy

    Given a binary tree, find its minimum depth.

    The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

    **Note:** A leaf is a node with no children.

     

    **Example 1:**

    ![img](https://assets.leetcode.com/uploads/2020/10/12/ex_depth.jpg)

    Input: root = [3,9,20,null,null,15,7]
    Output: 2
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19

    ```java
    class Solution {
         public int minDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftDepth = minDepth(root.left);
            int rightDepth = minDepth(root.right);
            if (root.left == null) {  //!!!!!!!!!
                return rightDepth + 1;
            }
            if (root.right == null) { //!!!!!!!!!
                return leftDepth + 1;
            }
            // 左右结点都不为null
            return Math.min(leftDepth, rightDepth) + 1;
        }
    }

222. Count Complete Tree Nodes

😭 Easy

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

Example 1:

img

1
2
Input: root = [1,2,3,4,5,6]
Output: 6
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int countNodes(TreeNode root) {
         if (root == null) {
            return 0;
        }
        //int left = 0, right = 0;
        //if(root.left != null)  left = countNodes(root.left) + 1;
        //if(root.right != null) right = countNodes(root.right) + 1;
        int left = countNodes(root.left) ; // dont +1, wrong!!!
        int right = countNodes(root.right) ;
        return left + right + 1;
    }
}

110. Balanced Binary Tree - tree height

😍Easy

Given a binary tree, determine if it is height-balanced.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Example 1:

img

1
2
Input: root = [3,9,20,null,null,15,7]
Output: true

高度，后序遍历。(本题)

深度，前序遍历。you can’t solve this problem by compare the depth of the left and right tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// my solution
class Solution {
    public boolean res = true;
    public boolean isBalanced(TreeNode root) {
        check(root);
        return res;
    }
    public int check(TreeNode root){
        if(root == null) return 0;
        int left =  check(root.left) + 1;
        int right = check(root.right) + 1; 
        if(Math.abs(left - right) > 1) res = false;
        return Math.max(left, 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
// daimasuixianglu
class Solution {
   /**
     * 递归法
     */
    public boolean isBalanced(TreeNode root) {
        return getHeight(root) != -1;
    }

    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        // 左右子树高度差大于1，return -1表示已经不是平衡树了
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}

257. Binary Tree Paths - tree depth

😍Easy

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

img

1
2
Input: root = [1,2,3,null,5]
Output: ["1->2->5","1->3"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<String> res = new LinkedList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null) return res;
        if(root.left == null  && root.right == null) {
            res.add("" + root.val);
            return res;
        }
        find(root.left, "" + root.val);
        find(root.right, "" + root.val);
        return res;
    }
    public void find(TreeNode node, String path){
        if(node != null){
            path += "->" + node.val; // mid
            find(node.left, path); //left
            find(node.right, path); //right
            if(node.left == null && node.right ==null) res.add(path);
        }else{
            
            return;
        }
    }
}

carl solution

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
// carl
class Solution {
    /**
     * 递归法
     */
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();// 存最终的结果
        if (root == null) {
            return res;
        }
        List<Integer> paths = new ArrayList<>();// 作为结果中的路径
        traversal(root, paths, res);
        return res;
    }

    private void traversal(TreeNode root, List<Integer> paths, List<String> res) {
        paths.add(root.val);// 前序遍历，中
        // 遇到叶子结点
        if (root.left == null && root.right == null) {
            // 输出
            StringBuilder sb = new StringBuilder();// StringBuilder用来拼接字符串，速度更快
            for (int i = 0; i < paths.size() - 1; i++) {
                sb.append(paths.get(i)).append("->");
            }
            sb.append(paths.get(paths.size() - 1));// 记录最后一个节点
            res.add(sb.toString());// 收集一个路径
            return;
        }
        // 递归和回溯是同时进行，所以要放在同一个花括号里
        if (root.left != null) { // 左
            traversal(root.left, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
        if (root.right != null) { // 右
            traversal(root.right, paths, res);
            paths.remove(paths.size() - 1);// 回溯
        }
    }
}

404. Sum of Left Leaves

😭😭😭 Easy

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Example 1:

img

1
2
3
Input: root = [3,9,20,null,null,15,7]
Output: 24
Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// first try, wrong
class Solution {
    
    public int sumOfLeftLeaves(TreeNode root) {
        return sum(root, 0);
    }
    public int sum(TreeNode node, int sum){
        if(node == null) return 0;

        int left = sum(node.left, sum);
        int right = sum(node.right, sum);
        if(node.left != null && node.left.left == null && node.left.right == null){
            sum += node.left.val;
            return sum; // dont return here
            /*
            Determine whether the current recursive call should return a value 
            	(e.g., if it's contributing to a sum) 
            or continue the recursion 
            	(if more exploration of the tree structure is needed).
            */
        } 
        return left + right ;
    }
}
//modify first attemp:
class Solution {
    
    public int sumOfLeftLeaves(TreeNode root) {
        return sum(root);
    }
    public int sum(TreeNode node){
        if(node == null) return 0;
        int left = sum(node.left); //left
        int right = sum(node.right); //right

        if(node.left != null && node.left.left == null && node.left.right == null){
            left =  node.left.val;
       
        } 

        return left + right ; //mid
    }
}

//solution:
class Solution { //post-order
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        if(root.left == null && root.right == null) return 0; /* 
        it's fine if you dont have this stopping condition, 
        but it gonna do one more loop which is not necessary 
        */
        int leftValue = sumOfLeftLeaves(root.left);  
        if (root.left != null && root.left.left == null && root.left.right == null) { 
            leftValue = root.left.val; // notice, here cant be return!!!!
        }// 左
        int rightValue = sumOfLeftLeaves(root.right);  // 右                                                    
        int sum =  leftValue + rightValue;  // 中
        return sum;
    }
}


class Solution2 {
    public int res = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) return 0;
        sum(root);
        return res;
    }

    public void sum(TreeNode node){
        if (node == null) {   //not node.left right == null !!!!!!!!!!!!!!!!!!!
            return; // Return if the current node is null
        }                      !!!!!!!!!!!!!!!!!!!
        if(node.left != null && node.left.left == null && node.left.right == null){
            res += node.left.val;
        }
        sum(node.left);
        sum(node.right);
    }
}

一定要通过父节点来判断其子节点是不是我们想要的元素

404 wrap up

In tree-related questions, particularly when dealing with recursion, it’s crucial to understand when to return a certain value. Here’s a summary:

  1. Base Case: Always define a base case for recursion. This is the stopping condition that prevents infinite recursion. Typically, it’s when you reach a leaf node or a null node in the tree.
  2. Determine Return Values:
    • For functions calculating a result (like sum of node values, count of nodes, etc.), decide what value to return at each recursive step.
    • If you need to accumulate a result (like in sum or count problems), return the partial result up the recursion stack.
    • If you’re searching for a particular node or property, decide what value represents success or failure and return accordingly.
  3. Conditional Checks:
    • In conditional checks within the recursive function, ensure you’re correctly identifying the condition you’re interested in.
    • If a condition is met, you may need to perform certain actions before continuing the recursion.
  4. Passing Information:
    • If you need to pass additional information or state between recursive calls, ensure it’s being handled correctly. This could be done via function parameters or by updating global or class-level variables (though the latter should be used sparingly).
  5. Returning Values vs. Continuing Recursion:
    • Determine whether the current recursive call should return a value (e.g., if it’s contributing to a sum) or continue the recursion (if more exploration of the tree structure is needed).

Applying these principles to your code, the mistake lies in prematurely returning the sum when encountering a left leaf node. Instead, the sum should be accumulated and then returned after both left and right subtrees are explored.

Here’s the corrected code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return sum(root);
    }

    public int sum(TreeNode node) {
        if (node == null) return 0;

        int leftSum = 0;
        if (node.left != null && node.left.left == null && node.left.right == null) {
            leftSum += node.left.val; // Accumulate left leaf node value
        }

        int leftSubtreeSum = sum(node.left); // Explore left subtree
        int rightSubtreeSum = sum(node.right); // Explore right subtree

        return leftSum + leftSubtreeSum + rightSubtreeSum; // Return sum
    }
}

Returning the sum when you encounter a left leaf node prematurely terminates the recursion and may lead to incorrect results. Let’s break down why this is problematic:

  1. Incomplete Traversal: Returning immediately when a left leaf node is found means you’re not exploring the entire tree. The recursive function should traverse the entire tree to compute the sum of all left leaves correctly.
  2. Ignoring Right Subtree: By returning early, you’re completely ignoring the right subtree of the current node. This could lead to missing out on potential left leaves in the right subtree, which should also be considered in the final sum.
  3. Accumulation Issue: If you return the sum immediately when encountering a left leaf node, you’re not correctly accumulating the sum of all left leaves. Each left leaf node’s value should contribute to the final sum, and prematurely returning may lead to missing out on some of these values.
  4. Incorrect Result: Due to the incomplete traversal and premature return, the final result may be incorrect. It won’t reflect the true sum of all left leaves in the tree.

To ensure the correct computation of the sum of all left leaves, it’s essential to explore both left and right subtrees completely before returning any value. This ensures that all relevant nodes are considered and that the sum is accurately calculated.

513. Find Bottom Left Tree Value 6/10/2024

😭😭😭Medium

Given the root of a binary tree, return the leftmost value in the last row of the tree.

Example 1:

img

1
2
Input: root = [2,1,3]
Output: 1

Example 2:

img

1
2
Input: root = [1,2,3,4,null,5,6,null,null,7]
Output: 7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    private int Deep = -1; //!!!!!!!!!!
    private int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        value = root.val;
        findLeftValue(root,0);
        return value;
    }

    private void findLeftValue (TreeNode root,int deep) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            if (deep > Deep) {
                value = root.val;
                Deep = deep;
            }
        }
        findLeftValue(root.left,deep + 1);
        findLeftValue(root.right,deep + 1);
    }
}

如何找最左边的呢？可以使用前序遍历（当然中序，后序都可以，因为本题没有 中间节点的处理逻辑，只要左优先就行），保证优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。 前中后序，都是优先遍历左节点。

To find the leftmost leaf node, we can employ preorder traversal (although inorder and postorder traversals would also suffice since this problem does not involve processing of intermediate nodes, prioritizing the left side suffices). Ensure left-first search and then record the deepest leaf node encountered. This will be the value of the leftmost leaf node in the last row of the tree.

112. Path Sum

Easy

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children

Example 1:

img

1
2
3
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean res = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        find(root, 0, targetSum);
        return res;
    }
    public void find(TreeNode node, int sum, int target){
        if(node == null ) return;
        sum += node.val;
        if(target == sum && node.left == null && node.right == null){
            res = true;
        } 
        find(node.left, sum, target);
        find(node.right, sum, target);
    }
}

我的方法会遍历每一个node，

carl的方法是遍历到符合条件的方法就停止了

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
// carl
class solution {
   public boolean haspathsum(treenode root, int targetsum) {
        if (root == null) {
            return false;
        }
        targetsum -= root.val; //!!!!
        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }
        if (root.left != null) { // 去掉这个if语句也是对的
            boolean left = haspathsum(root.left, targetsum);
            if (left) {      // 已经找到
                return true;
            }
        }
        if (root.right != null) { // 去掉这个if语句也是对的
            boolean right = haspathsum(root.right, targetsum);
            if (right) {     // 已经找到
                return true;
            }
        }
        return false;
    }
}



/////with recursion
class Solution {
    private boolean traversal(TreeNode cur, int count) {
        if (cur.left == null && cur.right == null && count == 0) {
            return true;
        }
        if (cur.left == null && cur.right == null) {
            return false;
        }

        if (cur.left != null) {
            count -= cur.left.val;
            if (traversal(cur.left, count)) {
                return true;
            }
            count += cur.left.val; //!!!!!!!!
        }

        if (cur.right != null) {
            count -= cur.right.val;
            if (traversal(cur.right, count)) {
                return true;
            }
            count += cur.right.val; //!!!!!!
        }

        return false;
    }

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        return traversal(root, sum - root.val);
    }
}

相信很多同学都会疑惑，递归函数什么时候要有返回值，什么时候没有返回值，特别是有的时候递归函数返回类型为bool类型。

那么接下来我通过详细讲解如下两道题，来回答这个问题：

再来看返回值，递归函数什么时候需要返回值？什么时候不需要返回值？这里总结如下三点：

  • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
  • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
  • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）

本篇通过leetcode上112. 路径总和 和 113. 路径总和ii 详细的讲解了 递归函数什么时候需要返回值，什么不需要返回值。

113. Path Sum II

Medium

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

img

1
2
3
4
5
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
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
class solution {
    public List<List<Integer>> pathsum(TreeNode root, int targetsum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res; // 非空判断

        List<Integer> path = new LinkedList<>();
        preorderdfs(root, targetsum, res, path);
        return res;
    }

    public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetsum 的路径
            if (targetsum - root.val == 0) {
                res.add(new ArrayList<>(path));
            }
            return; // 如果和不为 targetsum，返回
        }

        if (root.left != null) {
            preorderdfs(root.left, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }
}

106. Construct Binary Tree from Inorder and Postorder Traversal

Mediu

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

Example 1:

img

1
2
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
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
class Solution {
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }

        return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    }

    public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
        // 参数里的范围都是前闭后开
        if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }
        int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
        int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
        root.left = findNode(inorder, inBegin, rootIndex,
                            postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder, rootIndex + 1, inEnd,
                            postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

654. Maximum Binary Tree 6/11/2024

😭😭Medium

You are given an integer array nums with no duplicates. A maximum binary tree can be built recursively from nums using the following algorithm:

  1. Create a root node whose value is the maximum value in nums.
  2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
  3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

Return the maximum binary tree built from nums.

Example 1:

img

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]
Explanation: The recursive calls are as follow:
- The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5].
    - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1].
        - Empty array, so no child.
        - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1].
            - Empty array, so no child.
            - Only one element, so child is a node with value 1.
    - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is [].
        - Only one element, so child is a node with value 0.
        - Empty array, so no child.

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

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
48
49
50
51
52
53
54
// first try !!!wrong!!!
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {

        TreeNode root = new TreeNode();
        build(nums, 0, nums.length - 1, root);
        return root;

    }
    public TreeNode build(int[] nums, int start, int end, TreeNode node){
        if(start > end) return null; 
        int index = 0;
        int max = -1;
        for(int i = start ; i <= end; i++){
            if(nums[i] > max){
                index = i;
                max = nums[i];
                
            }
        }
        node.val = nums[index];
        node.left = build(nums, start, index, node.left);
        node.right = build(nums, index+1, end, node.right);
        return node;
    }
}
/*

The main issue in your implementation is that you are creating a TreeNode with a default constructor and then setting its value and children later, which can cause complications. Instead, you should create a new TreeNode instance directly within the build method. 

*/

// carl solution
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {   
        return build(nums, 0, nums.length - 1);
    }
    public TreeNode build(int[] nums, int start, int end){
        if(start > end) return null; 
        //if(start == end) return new TreeNode(nums[start]); //!! 不要这个也可以运行成功
        int index = start;
        int max = nums[start];
        for(int i = start ; i <= end; i++){
            if(nums[i] > max){
                index = i;
                max = nums[i];
            }
        }
        TreeNode node = new TreeNode(max);
        node.left = build(nums, start, index - 1);
        node.right = build(nums, index + 1, end);
        return node;
    }
}

617. Merge Two Binary Trees

Easy

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:

img

1
2
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

1
2
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
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 {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return build(root1, root2);
    }
    public TreeNode build(TreeNode root1, TreeNode root2){
        if(root1 == null && root2 == null) return null;
        TreeNode node = new TreeNode();
        if(root1 != null && root2 != null){
            node.val = root1.val + root2.val;
            
        }else if(root1 == null && root2 != null){
            node.val = root2.val;
            root1 = new TreeNode(0);
        }else{
           node.val = root1.val;
           root2 = new TreeNode(0);
        }
        node.left = build( root1.left,  root2.left);
        node.right = build( root1.right,  root2.right);
        return node;
    }

}

//carl's solution 
// more clean and simple oh wow
class Solution {
    // 递归
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        root1.val += root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;
    }
}

700. Search in a Binary Search Tree

Easy

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

Example 1:

img

1
2
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null) return null;

        if(root.val == val) return root;
        TreeNode left = searchBST(root.left, val); //！！！
        //我做的时候，忘记用left来hold the output of searchBST
         if (left != null) {
            return left; //！！
        }
        TreeNode right =searchBST(root.right, val);
        return right;
        
    }
}

很多录友写递归函数的时候 习惯直接写 searchBST(root->left, val)，却忘了 递归函数还有返回值。

递归函数的返回值是什么? 是 左子树如果搜索到了val，要将该节点返回。 如果不用一个变量将其接住，那么返回值不就没了。

所以要 result = searchBST(root->left, val)。

– carl

98. Validate Binary Search Tree

😭😭😭Medium

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

img

1
2
Input: root = [2,1,3]
Output: true
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
class Solution {
    // 递归
    TreeNode max;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST(root.left);
        if (!left) {
            return false;
        }
        // 中
        if (max != null && root.val <= max.val) { // notice it's <= not <
            return false;
        }
        max = root; // notice, here doesnt return true;
        /* or 
            if(max == null || root.val > max.val){
                max = root;
            }else{
                return false;
            }
        */
        // 右
        boolean right = isValidBST(root.right);
        return right;
    }
}
要知道**中序遍历**下，输出的二叉搜索树节点的数值是有序序列。

有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。

中序遍历，一直更新maxVal，一旦发现maxVal >= root->val，就返回false，注意元素相同时候也要返回false。

  • The issue with returning true immediately after setting max = root in your code is that it would prematurely end the recursive traversal of the binary tree, preventing the algorithm from checking the entire tree for BST validity.

    In a BST, it is crucial to ensure that for every node, all nodes in its left subtree are smaller, and all nodes in its right subtree are larger. This check must be applied to every node in the tree. By returning true immediately after updating max, you would stop the recursion and fail to verify the nodes in the right subtree.

530. Minimum Absolute Difference in BST 6/12/2024

Easy

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

img

1
2
Input: root = [4,2,6,1,3]
Output: 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    TreeNode pre;// 记录上一个遍历的结点
    int result = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
       if(root==null)return 0;
       traversal(root);
       return result;
    }
    public void traversal(TreeNode root){
        if(root==null)return;
        //左
        traversal(root.left);
        //中
        if(pre!=null){
            result = Math.min(result,root.val-pre.val); 
            // you dont need to cal the abs here because inorder traversal will return the ascending array
        }
        pre = root;
        //右
        traversal(root.right);
    }
}

题目中要求在二叉搜索树上任意两节点的差的绝对值的最小值。

注意是二叉搜索树，二叉搜索树可是有序的。

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了。

  • 如何记录前一个节点的指针，其实实现起来是很简单的

遇到在二叉搜索树上求什么最值，求差值之类的，都要思考一下二叉搜索树可是有序的，要利用好这一特点。

同时要学会在递归遍历的过程中如何记录前后两个指针，这也是一个小技巧，学会了还是很受用的。

501. Find Mode in Binary Search Tree

Easy

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
  • The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

img

1
2
Input: root = [1,null,2,2]
Output: [2]
  • 如果不是二叉搜索树

如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。

  • 二叉搜索树

这里其实只需要遍历一次就可以找到所有的众数。

那么如何只遍历一遍呢？

如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中。

万一，这个maxCount此时还不是真正最大频率呢。

所以下面要做如下操作：

频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。

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

class Solution {
    int maxc;
    int count;
    TreeNode pre;
    ArrayList<Integer> resl; // LinkedList also works
    public int[] findMode(TreeNode root) {
        maxc = 0;
        count = 0;
        resl = new ArrayList<>();
        find(root);
        int[] res = new int[resl.size()];
        for (int i = 0; i < resl.size(); i++) {
            res[i] = resl.get(i);
        }
        return res;
    }
    public void find(TreeNode node){
        if(node == null) return;
        find(node.left);
        if(pre == null || node.val != pre.val) count = 1; 			//!!!!!!! pre == null is for the first node
        //而且如果去掉pre ==null, 第二个pre.val会报错
        if(pre != null && pre.val == node.val) count++;
        if(count > maxc){
            resl.clear();
            resl.add(node.val);
            maxc = count;
        }else if(count == maxc){ //!!! cant use if here
            resl.add(node.val);
        }
        pre = node;

        find(node.right);
    }
}
1
2
3
4
5
6
7
8
      //explaination 
if (pre == NULL) { // 第一个节点
          count = 1;
      } else if (pre->val == cur->val) { // 与前一个节点数值相同
          count++;
      } else { // 与前一个节点数值不同
          count = 1;
      }

236. Lowest Common Ancestor of a Binary Tree

Medium

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

img

1
2
3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
1
2
3
4
5
6
7
8
9
10
11
12
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 right;
        if(left != null &&  right == null) return left;
        if(left != null &&  right != null) return root;
        return null; // for left == null && right == null
    }
}
  • why post order traversal?

both left and right subtrees need to be fully traversed before processing the current node.

the current node requires both its left and right subtrees to determine the lowest common ancestor (LCA), so left and right subtree need to be traversed first.

*

为什么left为空，right不为空，目标节点通过right返回呢？

如图：

explanation for 

     if(left == null &&  right != null) return right;
     if(left != null &&  right == null) return left;
     if(left != null &&  right != null) return root;

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

图中节点10的左子树返回null，右子树返回目标值7，那么此时节点10的处理逻辑就是把右子树的返回值（最近公共祖先7）返回上去！

这里也很重要，可能刷过这道题目的同学，都不清楚结果究竟是如何从底层一层一层传到头结点的。

那么如果left和right都为空，则返回left或者right都是可以的，也就是返回空。

那么寻找最小公共祖先，完整流程图如下：

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

  • 假如说p是q的父节点， 那其实算法走到p的时候就会直接返回，就不会再往下走了！！！

235. Lowest Common Ancestor of a Binary Search Tree 6/13/2024

😭 Medium

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

img

1
2
3
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val > q.val){
            TreeNode temp = p;
            p = q;
            q = temp;
        }
        return find(root, p, q);
    }
    public TreeNode find(TreeNode root, TreeNode p , TreeNode q){ // because we want to calculate the depth, so use post order tracversal
        if(root == null) return null;
        if(p.val <= root.val && q.val >= root.val) return root; //notice >= not just >, cause q might the the parent node of q
        TreeNode left = find(root.left, p, q);
        if(left != null) return left;
        TreeNode right = find(root.right, p, q);
        return right;
        
    }
}

如图，我们从根节点搜索，第一次遇到 cur节点是数值在[q, p]区间中，即 节点5，此时可以说明 q 和 p 一定分别存在于 节点 5的左子树，和右子树中。

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

此时节点5是不是最近公共祖先？ 如果 从节点5继续向左遍历，那么将错过成为p的祖先， 如果从节点5继续向右遍历则错过成为q的祖先。

所以当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[q, p]区间中，那么cur就是 q和p的最近公共祖先。

理解这一点，本题就很好解了。

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
// Carl solution

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private TreeNode traversal(TreeNode cur, TreeNode p, TreeNode q) {
        if (cur == null) return null;
        
        if (cur.val > p.val && cur.val > q.val) {
            TreeNode left = traversal(cur.left, p, q);
            if (left != null) {
                return left;
            }
        }

        if (cur.val < p.val && cur.val < q.val) {
            TreeNode right = traversal(cur.right, p, q);
            if (right != null) {
                return right;
            }
        }
        return cur;
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return traversal(root, p, q);
    }
}


  • 确定单层递归的逻辑

在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭又闭）

那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上）。

需要注意的是此时不知道p和q谁大，所以两个都要判断

代码如下：

1
2
3
4
5
6
if (cur->val > p->val && cur->val > q->val) {
    TreeNode* left = traversal(cur->left, p, q);
    if (left != NULL) {
        return left;
    }
}

细心的同学会发现，在这里调用递归函数的地方，把递归函数的返回值left，直接return。

在236. 二叉树：公共祖先问题 (https://programmercarl.com/0236.二叉树的最近公共祖先.html) 中，如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//236
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode 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) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点
            return right;
        }else if(left != null && right == null) { // 若找到一个节点
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }

搜索一条边的写法：
1
2
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;

My understanding: if theres returned value from root.left, then wont go into 递归函数(root->right)

搜索整个树写法：
1
2
3
left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;

本题就是标准的搜索一条边的写法，遇到递归函数的返回值，如果不为空，立刻返回。

如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树）。

1
2
3
4
5
6
if (cur->val < p->val && cur->val < q->val) {
    TreeNode* right = traversal(cur->right, p, q);
    if (right != NULL) {
        return right;
    }
}

剩下的情况，就是cur节点在区间（p->val <= cur->val && cur->val <= q->val）或者 （q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。

701. Insert into a Binary Search Tree

😭😭Medium

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Example 1:

img

1
2
3
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:
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
class Solution {
    
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            return new TreeNode(val); 
        }
        if(root.val < val){
            root.right = insertIntoBST(root.right, val);
        }
        
        if(root.val > val){
            root.left = insertIntoBST(root.left, val);
        }
        return root; //!!!向上一层返回root 
        //并不是只有最后一次final result 才return

    }
   
}

// easier to understand:
class Solution {
    
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null){
            return new TreeNode(val); 
        }
        if(root.val < val){
            root.right = insertIntoBST(root.right, val);
            return root; //!!
        }
        
        if(root.val > val){
            root.left = insertIntoBST(root.left, val);
            return root; //!!
        }
         
         
        return null;
    }
   
}

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。

插入任何一个节点，都可以在叶子节点上操作

450. Delete Node in a BST

😭😭Medium

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

  1. Search for a node to remove.
  2. If the node is found, delete the node.

Example 1:

img

1
2
3
4
5
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.

✨✨✨ think about how return statement work here✨✨✨

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
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) return null;
        if(root.val == key){
            if(root.left == null){
                return root.right;
            }else if (root.right == null){
                return root.left;
            }else{
                TreeNode temp = root.left;
                while(temp.right != null){
                    temp = temp.right;
                }
                temp.right = root.right;
                root = root.left; // delete root
                return root;
            }
            /* or
                }else {
                TreeNode cur = root.right;
                while (cur.left != null) {
                  cur = cur.left;
                }
                cur.left = root.left;
                root = root.right;
                return root;
              }
            
            */
        }
        if (root.val > key) root.left = deleteNode(root.left, key);
        if (root.val < key) root.right = deleteNode(root.right, key);
        return root;
    }
}
  • 确定单层递归的逻辑

这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了

  • 找到删除的节点

    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点

    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点

    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

读完本篇，大家会发现二叉搜索树删除节点比增加节点复杂的多。

因为二叉搜索树添加节点只需要在叶子上添加就可以的，不涉及到结构的调整，而删除节点操作涉及到结构的调整。

这里我们依然使用递归函数的返回值来完成把节点从二叉树中移除的操作。

这里最关键的逻辑就是第五种情况（删除一个左右孩子都不为空的节点），这种情况一定要想清楚。

而且就算想清楚了，对应的代码也未必可以写出来，所以这道题目既考察思维逻辑，也考察代码能力。

669. Trim a Binary Search Tree

😭😭 Medium

Given the root of a binary search tree and the lowest and highest boundaries as low and high, trim the tree so that all its elements lies in [low, high]. Trimming the tree should not change the relative structure of the elements that will remain in the tree (i.e., any node’s descendant should remain a descendant). It can be proven that there is a unique answer.

Return the root of the trimmed binary search tree. Note that the root may change depending on the given bounds.

Example 1:

img

1
2
Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return null;
        if(root.val < low){
            TreeNode right =  trimBST(root.right, low, high //！！
                            // cannot return root.right, not all the nodes in the right tree are qualified
            return right;
        }
        if(root.val > high){
            TreeNode left =  trimBST(root.left, low, high); //！！
            return left;
        }
        root.left = trimBST( root.left, low,  high);
        root.right = trimBST( root.right,  low,  high);
        return root;
    }
}

108. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/)

Easy

Given an integer array nums where the elements are sorted in ascending order, convert it to a *height-balanced* binary search tree.

Example 1:

img

1
2
3
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1); // 这个函数里面不需要传入treenode root,每个循环里面new一个就好
    }
    public TreeNode build(int[] nums, int start, int end){
        if(start > end) return null;
        int num = nums[(start + end) / 2];
        TreeNode node = new TreeNode(num);
        node.left = build(nums, start,(start + end) / 2 - 1);
        node.right = build(nums, (start + end) / 2 + 1, end);
        return node;
    }
}

在二叉树：构造二叉树登场！ 和 二叉树：构造一棵最大的二叉树之后，我们顺理成章的应该构造一下二叉搜索树了，一不小心还是一棵平衡二叉搜索树。

其实思路也是一样的，不断中间分割，然后递归处理左区间，右区间，也可以说是分治。

此时相信大家应该对通过递归函数的返回值来增删二叉树很熟悉了，这也是常规操作。

在定义区间的过程中我们又一次强调了循环不变量的重要性。

最后依然给出迭代的方法，其实就是模拟取中间元素，然后不断分割去构造二叉树的过程。

538. Convert BST to Greater Tree

😭😍😄Medium

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Example 1:

img

1
2
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
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
48
49
50
51
52
53
class Solution {
    int sum; //！！！！！！！！！！！！！！
    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        convertBST1(root);
        return root;
    }

    // 按右中左顺序遍历，累加即可 !!！！！！！！！！！！！！！！！！！
    public void convertBST1(TreeNode root) {
        if (root == null) {
            return;
        }
        convertBST1(root.right);
        sum += root.val;
        root.val = sum;
        convertBST1(root.left);
    }
}

// my method
class Solution {
    int sum;
    public TreeNode convertBST(TreeNode root) {
        sum = sum(root);
        System.out.println(sum);
        travel(root);
        return root;
    }
    // public int sum(TreeNode node, int sum){
    //     if(node == null) return 0;
    //     sum += node.val;
    //     sum += sum(node.left, sum);
    //     sum +=  sum(node.right, sum);
    //     return sum;
    // }
    public int sum(TreeNode node){
        if(node == null) return 0;
        int left= sum(node.left);
        int right =  sum(node.right);
        return left + right + node.val;
    }
    public  void travel(TreeNode node){
        if(node == null) return ;
        travel(node.left);
        int originalValue = node.val;
        node.val = sum;
        sum -= originalValue;
        travel(node.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
46
47
48
49
50
51
52
// first attemp wrong:
class Solution {
    public TreeNode convertBST(TreeNode root) {
        sum = sum(root);
        System.out.println(sum);
        travel(root, sum);
        return root;
    }

    public int sum(TreeNode node){
        if(node == null) return 0;
        int left= sum(node.left);
        int right =  sum(node.right);
        return left + right + node.val;
    }
    public  void travel(TreeNode node, int sum){
        if(node == null) return ;
        travel(node.left, sum);
        int originalValue = node.val;
        node.val = sum;
        sum -= originalValue;
        travel(node.right, sum);

    }
}  //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!worth thinking
//对比一下上面和下面的代码！！！！

//chatgpt modifies
class Solution {
    public TreeNode convertBST(TreeNode root) {
        int totalSum = sum(root); // 计算总和
        System.out.println(totalSum); // 打印总和（可选）
        travel(root, new int[]{totalSum}); // 遍历并转换树
        return root;
    }
    
    public int sum(TreeNode node){
        if(node == null) return 0;
        int left = sum(node.left); // 计算左子树总和
        int right = sum(node.right); // 计算右子树总和
        return left + right + node.val; // 返回当前节点及其子树的总和
    }
    
    public void travel(TreeNode node, int[] sum){
        if(node == null) return ;
        travel(node.left, sum); // 遍历左子树
        int originalValue = node.val; // 保存当前节点的原始值
        node.val = sum[0]; // 更新当前节点的值为累计和
        sum[0] -= originalValue; // 更新累计和（减去当前节点的原始值）
        travel(node.right, sum); // 遍历右子树
    }
}

！！！！！！！！！！！！！因为

  • void travel(TreeNode node, int sum) 每次传进去的是一个integer, 每个loop是在单独对这个独立的（不同的）integer做修改，每个loop里的integer的地址都是不一样的。

  • 但是如果把sum变成array，每次loop修改的是同一个地址里面的同一个数。

  • 或者把sum从function parameter里面一出来变成class-level parameter,这样每次修改的也是同一个数！