General

104 Max depth

public int maxDepth(TreeNode root) { if(root == null) return 0;

return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

}

111 Min depth

public int minDepth(TreeNode root) {
    if(root == null) return 0;
    if(root.left == null) return minDepth(root.right) + 1;
    if(root.right == null) return minDepth(root.left) + 1;

    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

110 Check Balanced

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

public boolean isBalanced(TreeNode root) {
    return maxDepth(root) == -1 ? false : true;
}

private int maxDepth(TreeNode root){
    if(root == null) return 0;

    int left = maxDepth(root.left);
    int right = maxDepth(root.right);

    if(left == -1 || right == -1 || Math.abs(left-right) > 1) return -1;

    return Math.max(left, right) + 1;
}

285 Inorder Successor/Predecessor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

• Successor

  public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if(root == null) return null;
    if(root.val <= p.val) return inorderSuccessor(root.right, p);
    else{
        TreeNode left = inorderSuccessor(root.left, p);
        return left == null ? root : left;
    }
  }

• Predecessor

  public TreeNode predecessor(TreeNode root, TreeNode p){
    if(root == null) return null;
    if(root.val >= p.val) return predecessor(root.left, p);
    else{
        TreeNode right= predecessor(root.right, p);
        return right==null? node : right;
    }
  }

654 Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.

2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.

3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

   • Divide and Conquer, use getTree construct tree and findMax find max index.

   • Average time O(nlogn), worst case O(n^2)

public TreeNode constructMaximumBinaryTree(int[] nums) {
    return getTree(nums, 0, nums.length);
}

private TreeNode getTree(int[] nums, int start, int end){
    if(start == end) return null;
    int max_idx = findMax(nums, start, end);
    TreeNode node = new TreeNode(nums[max_idx]);
    node.left = getTree(nums, start, max_idx);
    node.right = getTree(nums, max_idx+1, end);

    return node;
}

private int findMax(int[] nums, int start, int end){
    int max = nums[start];
    int index = start;
    for(int i= start+1; i<end; i++){
        if(nums[i] > max){
            max = nums[i];
            index = i;
        }
    } 
    return index;
}

222 Count Complete TreeNode

Given a complete binary tree, count the number of nodes.

• Time O(n)

public int countNodes(TreeNode root) {
    if(root == null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

• 每一層leftNode or rightNode有一個是complete tree, 總共logn層

• Time O(logn)

public int countNodes(TreeNode root) {
    int left = leftHeight(root);
    int right = rightHeight(root);

    if(left == right) return (1 << left) -1;
    return 1 + countNodes(root.left) + countNodes(root.right);
}

private int leftHeight(TreeNode node){
    int height = 0;
    while(node != null){
        height++;
        node = node.left;
    }
    return height;
}

private int rightHeight(TreeNode node){
    int height = 0;
    while(node != null){
        height++;
        node = node.right;
    }
    return height;
}

863. All Nodes Distance K in Binary Tree

Return a list of the values of all nodes that have a distance K from the target node.

"""
分target以上level跟以下level討論
1. 以下level找到distance為k的node
2. 往上recursive找到距離為k的upper level node, 繼續往上，網left and right node找
"""
class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
        self.ans = []
        self. dfs(root, target, K)
        return self.ans
    
    # return the distance to node target
    def dfs(self, node, target, K):
        if not node:
            return -1
        elif node == target:
            self.addNodes(node, K)
            return 1
        else:
            L, R = self.dfs(node.left, target, K), self.dfs(node.right, target, K)
            if L != -1 and L <= K:
                if L == K:
                    self.ans.append(node.val)
                # target 在left child, 往 right child 移動
                self.addNodes(node.right, K-L-1)
                return L+1
            elif R != -1 and R<=K:
                if R == K:
                    self.ans.append(node.val)
                self.addNodes(node.left, K-R-1)
                return R+1
            else:
                return -1
            
    def addNodes(self, node, K):
        if not node:
            return 
        if K==0:
            self.ans.append(node.val)
            
        self.addNodes(node.left, K-1)
        self.addNodes(node.right, K-1)

1145. Binary Tree Coloring Game

Two players play a turn based game on a binary tree. We are given the root of this binary tree, and the number of nodes n in the tree. n is odd, and each node has a distinct value from 1 to n.

The first player colors the node with value x red, and the second player colors the node with value y blue.

return if second player can win the game

• The best chance to win is choosing node next to x, the players 1 can't cross this node, players can take the child nodes all.

• 3 possibilities: left child, right child, and parent node

• Return if candidate subtree is greater than total number of nodes

def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
    l, r = 0, 0
    def count(node):
        nonlocal l, r
        if not node: return 0
        left = count(node.left)
        right = count(node.right)
         
        # meet x node, update the left child and right child candidate 
        if node.val == x:
            l, r = left, right
        return 1 + left + right
    total = count(root)
    return max(max(l, r), n - l - r - 1) > total // 2