Tree

Cheat Sheet

Explanation

Iterative

Binary Tree Traversal

144. Binary Tree Preorder Traversal

# ITERATION
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        if not root:
            return res
        stack.append(root)
        while stack:
            curt = stack.pop()
            res.append(curt.val)
            if curt.right:
                stack.append(curt.right)
            if curt.left:
                stack.append(curt.left)
        return res

# RECURSION
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res):
        if root == None:
            return
        res.append(root.val)
        self.helper(root.left, res)
        self.helper(root.right, res)

94. Binary Tree Inorder Traversal

# ITERATION
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        if not root:
            return res
        self.addLeft(root, stack)
        while stack:
            curt = stack.pop()
            res.append(curt.val)
            self.addLeft(curt.right, stack)
        return res
    
    def addLeft(self, curt, stack):
        while curt:
            stack.append(curt)
            curt = curt.left

# RECURSION
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res) -> None:
        if root == None:
            return
        self.helper(root.left, res)
        res.append(root.val)   
        self.helper(root.right, res)

145. Binary Tree Postorder Traversal

# ITERATION
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = []
        res = []
        if not root:
            return res
        stack.append(root)
        while stack:
            curt = stack.pop()
            res.append(curt.val)
            if curt.left:
                stack.append(curt.left)
            if curt.right:
                stack.append(curt.right)
        res.reverse()
        return res
        
# RECURSION
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        res = []
        self.helper(root, res)
        return res
    
    def helper(self, root, res):
        if root == None:
            return
        self.helper(root.left, res)
        self.helper(root.right, res)
        res.append(root.val)  

226. Invert Binary Tree

Swap left node with right node.

    def invertTree(self, root: TreeNode) -> TreeNode:
        self.helper(root)
        return root
    
    def helper(self, root) :
        if not root:
            return
        temp = root.right
        root.right = root.left
        root.left = temp
        self.helper(root.left)
        self.helper(root.right)

104. Maximum Depth of Binary Tree

Top - down

    res = 0
    def maxDepth(self, root: TreeNode) -> int:
        self.helper(root, 1)
        return self.res
    
    
    def helper(self, curt, depth):
        if not curt:
            return
        self.res = max(self.res, depth)
        self.helper(curt.left, depth + 1)
        self.helper(curt.right, depth + 1)

Bottom - up

    def maxDepth(self, root: TreeNode) -> int:
        return self.helper(root, 1)
    
    def helper(self, curt, depth):
        if not curt:
            return 0
        L = self.helper(curt.left, depth + 1)
        R = self.helper(curt.right, depth + 1)
        return max(max(L, R), depth)

559. Maximum Depth of N-ary Tree

public int maxDepth(Node root) {
    return helper(root);
}

private int helper(Node curt) {
    if (curt == null) return 0;
    int max = 0;
    for (Node child : curt.children) {
        max = Math.max(max, helper(child));
    }
    return max + 1;
}

257. Binary Tree Paths

Java

    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) return res;
        dfs(root, new StringBuilder(), res);
        return res;
    }
    
    private void dfs(TreeNode root, StringBuilder sb, List<String> res) {
        if (root == null) return;
        if (root.left == null && root.right == null) {
            sb.append(root.val);
            res.add(sb.toString());
            return;
        }
        sb.append(root.val).append("->");
        int len = sb.length();
        dfs(root.left, sb, res);
        sb.setLength(len);
        dfs(root.right, sb, res);
    }

Python

    def binaryTreePaths(self, root: TreeNode) -> List[str]:
        result = []
        self.helper(root, "", result)
        return result
    
    def helper(self, root, curt, res):
        if not root:
            return
        if not root.left and not root.right:
            curt += str(root.val)
            res.append(curt)
            return 
        curt += str(root.val) + "->"
        self.helper(root.left, curt, res)
        self.helper(root.right, curt, res)
        

100. Same Tree

101. Symmetric Tree

572. Subtree of Another Tree

    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (s == null) return false;
        return isSame(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }
    
    private boolean isSame(TreeNode s, TreeNode t) {
        if (s == null && t == null) return true;
        if (s == null || t == null) return false;
        return s.val == t.val && isSame(s.left, t.left) && isSame(s.right, t.right);
    }

110. Balanced Binary Tree

把左边和右边的结果放到一个variable存一下，看看是不是哪边=-1或者两边的差大约1

    res = True
    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        self.helper(root)
        return self.res
    
    def helper(self, curr):
        if not curr:
            return 0
        L = self.helper(curr.left)
        R = self.helper(curr.right)
        self.res = (abs(L - R) <= 1) and self.res
        return max(L, R) + 1

236. Lowest Common Ancestor of a Binary Tree

Bottom-up and detect the node is on both L and R or just one side?

Java

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode L = lowestCommonAncestor(root.left, p, q);
        TreeNode R = lowestCommonAncestor(root.right, p, q);
        if (L != null && R != null) {
            return root;
        } else if (L == null && R != null) {
            return R;
        } else if (L != null && R == null) {
            return L;
        } 
        return null;
    }

Python

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root:
            return None
        if root == p or root == q:
            return root
        L = self.lowestCommonAncestor(root.left, p, q)
        R = self.lowestCommonAncestor(root.right, p, q)
        if L and R:
            return root
        if L and not R:
            return L
        if not L and R:
            return R
        return None

112. Path Sum

Traverse to see if a leaf node value equals sum, deduct current node val on each node.

Java

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

Python

    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return sum == root.val
        sum -= root.val
        return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

113. Path Sum II

Traverse down the tree, add new node value to the list. Deep copy current list on each level.

Java

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        helper(root, sum, new ArrayList<>(), result);
        return result;
    }
    
    private void helper(TreeNode root,
                        int sum,
                        List<Integer> curtList, 
                        List<List<Integer>> res) {
        if (root == null) return;
        curtList.add(root.val);
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                res.add(new ArrayList<>(curtList));
            }
            return;
        }
        helper(root.left, sum - root.val, new ArrayList<>(curtList), res);
        helper(root.right, sum - root.val, new ArrayList<>(curtList), res);
    }

Python

    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        self.helper(root, [], res, sum)
        return res
        
    def helper(self, root, curt, res, sum):
        if not root:
            return
        curt.append(root.val)
        if not root.left and not root.right and sum == root.val:
            res.append(copy.deepcopy(curt))
        self.helper(root.left, curt, res, sum - root.val)
        self.helper(root.right, curt, res, sum - root.val)
        curt.pop()

Python (deep copy on each level)

    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        self.helper(root, [], res, sum)
        return res
        
    def helper(self, root, curt, res, sum):
        if not root:
            return
        curt.append(root.val)
        sum -= root.val
        if not root.left and not root.right:
            if sum == 0:
                res.append(copy.deepcopy(curt) )
            return
        self.helper(root.left, copy.deepcopy(curt), res, sum)
        self.helper(root.right, copy.deepcopy(curt), res, sum)

This version of backtracking. No need to make a deep-copy of the current list.

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        helper(root, sum, new ArrayList<>(), result);
        return result;
    }
    
    private void helper(TreeNode root,
                        int sum,
                        List<Integer> curtList, 
                        List<List<Integer>> res) {
        if (root.left == null && root.right == null) {
            if (sum == root.val) {
                curtList.add(root.val);
                res.add(new ArrayList<>(curtList));
                curtList.remove(curtList.size() - 1);
            }
            return;
        }
        curtList.add(root.val);
        if (root.left != null) helper(root.left, sum - root.val, curtList, res);
        if (root.right != null) helper(root.right, sum - root.val, curtList, res);
        curtList.remove(curtList.size() - 1);
    }

437. Path Sum III

This question asks all Path Sum starting any node to any node, but only go downwards. It can be easily achieved by using the previous method + start fresh traversal at each node.

T: O(n^2)

    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return helper(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    
    private int helper(TreeNode root, int sum) {
        if (root == null) return 0;
        int count = 0;
        if (sum == root.val) count += 1;
        count += helper(root.left, sum - root.val);
        count += helper(root.right, sum - root.val);
        return count;
    }

This can also achieved by using PrefixSum. Maintain a current sum and count of the prefix sum numbers in a HashMap ( key : the prefix sum, value : how many ways get to this prefix sum). Add the node value to the prefix sum. curtSum - target indicates that theres is a range sum in the path equals to target. Put curtSum in the map. When backtracking, reduce a count by 1 as it shouldn't count the current node anymore.

This method is very similar with LC560.

Java

    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return helper(root, sum, 0, map);
    }
    
    private int helper(TreeNode root, 
                       int target, 
                       int curtSum, 
                       Map<Integer, Integer> map) {
        if (root == null) return 0;
        curtSum += root.val;
        int count = map.getOrDefault(curtSum - target, 0);
        map.put(curtSum, map.getOrDefault(curtSum, 0) + 1);
        count += helper(root.left, target, curtSum, map) + helper(root.right, target, curtSum, map);
        map.put(curtSum, map.get(curtSum) - 1);
        return count;
    }

Java (top-down)

Map<Integer, Integer> map = new HashMap<>();
int res = 0;
public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    map.put(0, 1);
    helper(root, sum, 0);
    return res;
}

private void helper(TreeNode root, int k, int sum) {
    if (root == null) return;
    sum += root.val;
    if (map.containsKey(sum - k)) {
        res += map.get(sum - k);
    }
    map.put(sum, map.getOrDefault(sum, 0) + 1);
    helper(root.left, k, sum);
    helper(root.right, k, sum);
    map.put(sum, map.getOrDefault(sum, 0) - 1);
}

298. Binary Tree Longest Consecutive Sequence

Java

    int max = Integer.MIN_VALUE;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        helper(root, 0 , root.val);
        return max;
    }

    private void helper(TreeNode root, int curtLength, int target) {
        if (root == null) return;
        curtLength = (root.val == target) ? curtLength + 1 : 1;
        max = Math.max(max, curtLength);
    
        helper(root.left, curtLength, root.val + 1);
        helper(root.right, curtLength, root.val + 1);
    }

Java (Top-Down with Parent)

    int max = 1;
    public int longestConsecutive(TreeNode root) {
        if (root == null) return 0;
        helper(root, null, 1);
        return max;
    }
    
    private void helper(TreeNode root, TreeNode parent, int seq) {
        if (root == null) {
            return;
        }
        if (parent != null && root.val == parent.val + 1) {
            max = Math.max(max, seq + 1);
            helper(root.left, root, seq + 1);
            helper(root.right, root, seq + 1);
        } else {
            helper(root.left, root, 1);
            helper(root.right, root, 1);
        }
    }

Java (Bottom-Up)

    int max = 1;
    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        helper(root);
        return max;
    }
    
    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, null);
        }
        Result L = helper(root.left);
        Result R = helper(root.right);
        int seq = 1;
        if (L.node != null && L.node.val == root.val + 1) {
            seq = Math.max(seq, L.seq + 1);
        }
        if (R.node != null && R.node.val == root.val + 1) {
            seq = Math.max(seq, R.seq + 1);
        }
        max = Math.max(max, seq);
        return new Result(seq, root);
    }
    
    class Result {
        int seq;
        TreeNode node;
        Result(int seq, TreeNode node) {
            this.seq = seq;
            this.node = node;
        }
    }

Java (Bottom-up no Global)

    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return helper(root).max;
    }
    
    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, 0, null);
        }
        Result L = helper(root.left);
        Result R = helper(root.right);
        int seq = 1;
        if (L.node != null && L.node.val == root.val + 1) {
            seq = Math.max(seq, L.seq + 1);
        }
        if (R.node != null && R.node.val == root.val + 1) {
            seq = Math.max(seq, R.seq + 1);
        }
        int max = Math.max(Math.max(L.max, R.max), seq);
        return new Result(seq, max, root);
    }
    
    class Result {
        int seq;
        int max;
        TreeNode node;
        Result(int seq, int max, TreeNode node) {
            this.seq = seq;
            this.node = node;
            this.max = max;
        }
    }

549. Binary Tree Longest Consecutive Sequence II

    public int longestConsecutive(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return helper(root).max;
    }
    
    private Result helper(TreeNode root) {
        if (root == null) {
            return new Result(0, 0, 0, null);
        }
        Result L = helper(root.left);
        Result R = helper(root.right);
        int Linc = 1, Ldec = 1, Rinc = 1, Rdec = 1;
        if (L.node != null) {
            if (L.node.val == root.val + 1) {
                Ldec = L.dec + 1;
            } else if (L.node.val == root.val - 1) {
                Linc = L.inc + 1;
            }
        }
        if (R.node != null) {
            if (R.node.val == root.val + 1) {
                Rdec = R.dec + 1;
            } else if (R.node.val == root.val - 1) {
                Rinc = R.inc + 1;
            }
        }
        int max = 1;
        int maxInc = Math.max(Linc, Rinc), maxDec = Math.max(Ldec, Rdec);
        max = Math.max(Math.max(maxInc, maxDec), max);
        max = Math.max(Math.max(Linc + Rdec - 1, Rinc + Ldec - 1), max);
        max = Math.max(Math.max(L.max, R.max), max);
        return new Result(maxInc, maxDec, max, root);
    }
    
    class Result {
        int inc, dec;
        int max;
        TreeNode node;
        Result(int inc, int dec, int max, TreeNode node) {
            this.inc = inc;
            this.dec = dec;
            this.max = max;
            this.node = node;
        }
    }

124. Binary Tree Maximum Path Sum

Java

    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(helper(root.left), 0);
        int right = Math.max(helper(root.right), 0);
        max = Math.max(max, left + right + root.val);
        return Math.max(left, right) + root.val;
    }

Python

class Result:
    def __init__(self, maxSum, singlePathSum):
        self.maxSum = maxSum
        self.singlePathSum = singlePathSum
    
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        return self.helper(root).maxSum
    
    def helper(self, root):
        if not root:
            return Result(-sys.maxsize, 0)
        L = self.helper(root.left)
        R = self.helper(root.right)
        lInt = max(L.singlePathSum, 0)
        rInt = max(R.singlePathSum, 0)
        return Result(max(lInt + rInt + root.val, max(L.maxSum, R.maxSum)), 
                      max(lInt, rInt) + root.val)

Python (global max)

    res = -sys.maxsize
    def maxPathSum(self, root: TreeNode) -> int:
        self.helper(root)
        return self.res
    
    def helper(self, root):
        if not root:
            return 0
        L = max(self.helper(root.left), 0)
        R = max(self.helper(root.right), 0)
        self.res = max(self.res, L + R + root.val)
        return max(L, R) + root.val

543. Diameter of Binary Tree

Bottom-up and return the longest path from bottom, which is Math.max(L, R) + 1. In addition, each node can be a potential root of the best result, therefore update the global max at each node by max = Math.max(L + R, max)

T: O(n) S: O(n)

Top - down

    int max = 0;
    Map<TreeNode, Integer> map;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        map = new HashMap<>();
        helper(root);
        return max;
    }
    
    private void helper(TreeNode root) {
        if (root == null) return;
        max = Math.max(max, maxPath(root.left) + maxPath(root.right));
        helper(root.left);
        helper(root.right);
    }
    
    private int maxPath(TreeNode root) {
        if (root == null) return 0;
        if (map.containsKey(root)) return map.get(root);
        int res = Math.max(maxPath(root.left), maxPath(root.right)) + 1;
        map.put(root, res);
        return res;
    }

Bottom - up

Java

    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        helper(root);
        return max;
    }
    
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int L = helper(root.left);
        int R = helper(root.right);
        max = Math.max(L + R, max);
        return Math.max(L, R) + 1;
    }

Python

class Result:
    def __init__(self, maxLen, singleLen):
        self.maxLen = maxLen
        self.singleLen = singleLen
            
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        return self.helper(root).maxLen
        
    def helper(self, root):
        if not root:
            return Result(0, 0)
        L = self.helper(root.left)
        R = self.helper(root.right)
        curtMax = max(L.singleLen + R.singleLen, max(L.maxLen, R.maxLen))
        return Result(curtMax, max(L.singleLen, R.singleLen) + 1)

Python (global max)

    res = 0
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.helper(root)
        return self.res
        
    def helper(self, root):
        if not root:
            return 0
        L = self.helper(root.left)
        R = self.helper(root.right)
        self.res = max(L + R, self.res)
        return max(L, R) + 1

117. Populating Next Right Pointers in Each Node II

Level order traversal and connect next nodes

T: O(n) S: O(n)

    public Node connect(Node root) {
        if (root == null) return null;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node prev = queue.poll();
            if (prev.left != null) queue.offer(prev.left);
            if (prev.right != null) queue.offer(prev.right);
            for (int i = 1; i < size; i++) {
                Node curt = queue.poll();
                if (curt.left != null) queue.offer(curt.left);
                if (curt.right != null) queue.offer(curt.right);
                prev.next = curt;
                prev = curt;
            }
        }
        return root;
    }

Iterative connection:

• head to represent the first node of the next level

• prev to represent the previous node (similar as linkedlist)

• curt to represent the current node (similar as linkedlist)

Use curt to traverse in each level, and connect the children. If the left/right child exist, and prev is not null, then use prev to connect. Otherwise if prev is null, it means that node is head.

T: O(n) S: O(1)

    public Node connect(Node root) {
        if (root == null) return null;
        Node head = root;
        Node prev = null;
        Node curt = null;
        while (head != null) {
            curt = head;
            prev = null;
            head = null;
            while (curt != null) {
                if (curt.left != null) {
                    if (prev != null) {
                        prev.next = curt.left;
                    } else {
                        head = curt.left;
                    }
                    prev = curt.left;
                }
                if (curt.right != null) {
                    if (prev != null) {
                        prev.next = curt.right;
                    } else {
                        head = curt.right;
                    }
                    prev = curt.right;
                }
                curt = curt.next;
            }
        }
        return root;
    }

662. Maximum Width of Binary Tree

Top-down traverse. Map the tree node position to an array, which means the left node is pos * 2 and right node pos is pos * 2 + 1. In preorder traversal, you will encounter the left most node, hence record the pos of the node in the Hashmap.

For the rest of nodes, the width will be right pos - left + 1. Update the global max on each node.

    int max = 1;
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        helper(root, map, 0, 0);
        return max;
    }
    
    private void helper(TreeNode root, 
                        Map<Integer, Integer> map, 
                        int depth,
                        int pos) {
        if (root == null) return;
        map.putIfAbsent(depth, pos);
        max = Math.max(max, pos - map.get(depth) + 1);
        helper(root.left, map, depth + 1, pos * 2);
        helper(root.right, map, depth + 1, pos * 2 + 1);
    }

Traversal Time Complexity:

For a Graph, the complexity of a Depth First Traversal is O(n + m), where n is the number of nodes, and m is the number of edges.

Since a Binary Tree is also a Graph, the same applies here. The complexity of each of these Depth-first traversals is O(n+m).

Since the number of edges that can originate from a node is limited to 2 in the case of a Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the total number of nodes.

The complexity then becomes O(n + n-1), which is O(n).

987. Vertical Order Traversal of a Binary Tree

Build coordinates of each node, sort by y and node val.

    int minX = 0;
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Map<Integer, List<Node>> map = new HashMap<>();
        dfs(root, 0, 0, map);
        for (int key : map.keySet()) {
            Collections.sort(map.get(key), new Comparator<Node>(){
                public int compare(Node a, Node b) {
                    if (a.y == b.y) return a.node.val - b.node.val;
                    return a.y - b.y;
                }
            });
            int xIndex = map.get(key).get(0).x - minX;
            while (res.size() <= xIndex) res.add(new ArrayList<>());
            for (Node n : map.get(key)) {
                res.get(xIndex).add(n.node.val);
            }
        }
        return res;
    }
    
    private void dfs(TreeNode root, int x, int y, Map<Integer, List<Node>> map) {
        if (root == null) return;
        minX = Math.min(minX, x);
        map.putIfAbsent(x, new ArrayList<>());
        Node node = new Node(root, x, y);
        map.get(x).add(node);
        dfs(root.left, x - 1, y + 1, map);
        dfs(root.right, x + 1, y + 1, map);
    }
    
    class Node {
        int x, y;
        TreeNode node;
        Node(TreeNode n, int x, int y) {
            this.node = n;
            this.x = x;
            this.y = y;
        }
    }

Delete a Node in Binary Tree

1. Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete.

2. Replace the deepest rightmost node’s data with node to be deleted.

3. Then delete the deepest rightmost node.

Binary Search Tree

• Search & Insert
• Delete

  • Four Key factors:

    • IS NOT IN A TREE: do nothing

    • IS A LEAF: just remove it

    • HAS ONLY ONE CHILD: Copy the child to the node and delete the child

    • HAS TWO CHILDREN: Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor. Note that inorder predecessor can also be used.
• 450. Delete Node in a BST

• Morris Traversal

250. Count Univalue Subtrees

用Boolean来记录左边和右边的结果，看是不是univalue subtrees，如果左边右边都是的话，Count++，返回True。如果左边右边都是，但是两边有Null或者值不等于Root Value，返回False

if (node == null) return true;

boolean left = helper(node.left);

boolean right = helper(node.right);

if (left && right) {

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

return false;

}

count++;

return true;

}

return false;

366. Find Leaves of Binary Tree

用Level来记录从下往上的层数，最下面Null是-1，往上是0，这样的话可以用res.get(level).add(curt.val) 来往结果里加值。如果结果里Array数小于level + 1说明没有那个Array，要建个新的

if (curt == null) return -1;

int level = 1 + Math.max(helper(curt.left, res), helper(curt.right, res));

if (res.size() < level + 1) {

res.add(new ArrayList<>());

}

res.get(level).add(curt.val);

return level;

337. House Robber III

有很多重复运算，因为要先算所有include 自己的情况，然后exclude自己的情况，取Max。解

• Improvement: 用Hashmap可以记录每个点的max
• Improvement： 用Array

107. Binary Tree Level Order Traversal II

• 用Queue的话，和I不一样的地方就是这个在上面插入List。result.add(0,list);

• 用Recursion，

if(level >= list.size()) {

list.add(0, new LinkedList<Integer>());

}

levelMaker(list, root.left, level+1);

levelMaker(list, root.right, level+1);

list.get(list.size()-level-1).add(root.val);

199. Binary Tree Right Side View

• Queue是用i == qSize - 1判断最右边

• Recursion用currDepth == result.size()判断最右边，然后每下一层depth + 1

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, 0, res);
        return res;
    }
    
    private void dfs(TreeNode root, int depth, List<Integer> res ) {
        if (root == null) return;
        if (depth == res.size()) {
            res.add(root.val);
        }
        dfs(root.right, depth + 1, res);
        dfs(root.left, depth + 1, res);
    }

572.Subtree of Another Tree

1120. Maximum Average Subtree

Bottom up to get the answer.

double res = Double.MIN_VALUE;
public double maximumAverageSubtree(TreeNode root) {
    helper(root);
    return res;
}

private int[] helper(TreeNode root) {
    if (root == null) {
        return new int[2];
    }
    int[] L = helper(root.left);
    int[] R = helper(root.right);
    int sum = L[0] + R[0] + root.val;
    int count = L[1] + R[1] + 1;
    res = Math.max(res, (double)sum / (double)count);
    return new int[]{sum, count};
}

114.Flatten Binary Tree to Linked List

108.Convert Sorted Array to Binary Search Tree

• • Use left, right, mid

    • If left > right -> return null

    • If left == right -> return nums[left]

    • Return root = new TreeNode(nums[mid]);

    • Root.left = helper(nums, left, mid - 1);

    • Root.right = helper(nums, mid + 1, right);

  • pre-order → build tree

  • post-order array → build tree

109. Convert Sorted List to Binary Search Tree

• Get size of the sorted list

• In recursive function:

  • TreeNode left = helper(0 to mid - 1)

  • find mid, construct the node by using mid

  • Node.left = left;

  • Node right = helper(mid + 1, end);

297.Serialize and Deserialize Binary Tree

• Construct a tree by using Root, left, right

• If (root == null) return “null” + “,”

• Str += String.valueOf(root.val) + “,”; Str = helper(root.left, str); str = helper(root.right, str);

• When de-serialization, split str by “,” and convert to LinkedList;

• Construct root from the first value, remove first value from List

• Go left and right

173. Binary Search Tree Iterator

• BST to Linkedlist by using Inorder traversal, create an iterator from the linkedlist

• Stack

• Morris traversal. Solution, Explanation

230. Kth Smallest Element in a BST

• Stack

• Morris

• Divide and conquer

285. Inorder Successor in BST

• Recursive to get inorder Successor & predecessor
• Iterative

270. Closest Binary Search Tree Value

272. Closest Binary Search Tree Value II

99. Recover Binary Search Tree

• In-order traversal
• Morris Traversal

156. Binary Tree Upside Down

Traverse to left and your returned non-null node is your new root. Connect the right of the current node to the left of the left node, connect current to the right of the left node. Erase root's left and right to null. Return new root.

public TreeNode upsideDownBinaryTree(TreeNode root) {
    if (root == null) return null;
    if (root.left == null && root.right == null) {
        return root;
    }
    TreeNode newRoot = upsideDownBinaryTree(root.left);
    root.left.left = root.right;
    root.left.right = root;
    root.left = null;
    root.right = null;
    return newRoot;
}

114. Flatten Binary Tree to Linked List

255. Verify Preorder Sequence in Binary Search Tree

333. Largest BST Subtree

Top-down method may take more than O(n) time. Use Bottom-up, and store if the branch is a BST, size of the BST, the min and max node. Return to the previous level. At each node:

• check if the left result and right result is a BST, if one of them is not, return the best count of left and right

• check if the curt.val exceed the range of left and right, if yes, return the best count of left and right

• return the result if current node is a root of a BST.

    public int largestBSTSubtree(TreeNode root) {
        return helper(root).count;
    }
    
    private Result helper(TreeNode curt) {
        if (curt == null) return new Result(true, 0);
        Result L = helper(curt.left);
        Result R = helper(curt.right);
        Result res = new Result(false, Math.max(L.count, R.count));
        if (!L.isBST || !R.isBST) {
            return res;
        } 
        if ((L.max != null && L.max.val >= curt.val) 
            || (R.min != null && R.min.val <= curt.val)) {
            return res;
        }
        res.isBST = true;
        res.count = L.count + R.count + 1;
        res.max = R.max != null ? R.max : curt;
        res.min = L.min != null ? L.min : curt;
        return res;
    }
    
    
    class Result {
        int count;
        boolean isBST;
        TreeNode max;
        TreeNode min;
        public Result(boolean isBST, int count) {
            this.isBST = isBST;
            this.count = count;
            this.max = null;
            this.min = null;
        }
    }

222. Count Complete Tree Nodes

105. Construct Binary Tree from Preorder and Inorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

116 .Populating Next Right Pointers in Each Node

Level order traversal, use a Prev == null before each level, if (prev != null) prev.next = curt, then curt = prev;

314. Binary Tree Vertical Order Traversal

• Use Map<Integer, List<Integer>> to store col and related nodes;

  • Add two queues, one to store nodes, the other one to store col, poll from two nodes at the same time. Default col with 0;

  • Keep a min and max to store the min and max col number

  • Convert the map to List<List<Integer>>

95. Unique Binary Search Trees II

用从1到N的数Construct所有Unique的BST

• If n == 0 return empty result

• Use helper function to iterate i through from 1 to n. Use another two iterations from 1 to i - 1 to create lefts and and i + 1 to n to create rights. Create node by using i, then attach root.left as left, root.right as right.

331. Verify Preorder Serialization of a Binary Tree

• Count indegree & outdegree
• Using stack

1110. Delete Nodes And Return Forest

Bottom-up approach. If curt need to be deleted, add left and right to the list.

Java

    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        Set<Integer> set = new HashSet<>();
        for (int node : to_delete) {
            set.add(node);
        }
        List<TreeNode> res = new ArrayList<>();
        root = helper(root, set, res);
        if (root != null) res.add(root);
        return res;
    }
     
    private TreeNode helper(TreeNode curt,
                        Set<Integer> toDelete, 
                        List<TreeNode> list) {
        if (curt == null) return null;
        TreeNode L = helper(curt.left, toDelete, list);
        TreeNode R = helper(curt.right, toDelete, list);
        if (toDelete.contains(curt.val)) {
            if (L != null) list.add(L);
            if (R != null) list.add(R);
            return null;
        } 
        curt.left = L;
        curt.right = R;
        return curt;
    }

Python

    def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
        res = []
        self.helper(root, to_delete, res)
        if root.val not in to_delete:
            res.append(root)
        return res
    
    def helper(self, root, to_delete, res):
        if not root:
            return None;
        root.left = self.helper(root.left, to_delete, res)
        root.right = self.helper(root.right, to_delete, res)
        if root.val in to_delete:
            if root.left:
                res.append(root.left)
            if root.right:
                res.append(root.right)
            return None
        else:
            return root

979. Distribute Coins in Binary Tree

    int total = 0;
    public int distributeCoins(TreeNode root) {
        helper(root);
        return total;
    }
    
    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int L = helper(root.left);
        int R = helper(root.right);
        int res = L + R + root.val;
        if (res == 1) {
            return 0;
        } 
        total += Math.abs(res - 1);
        return res - 1;
    }

863. All Nodes Distance K in Binary Tree

Convert tree to graph and BFS level order traversal.

    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, Set<TreeNode>> map = new HashMap<>();
        traverse(root, null, map);
        Queue<TreeNode> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        List<Integer> res = new ArrayList<>();
        q.offer(target);
        visited.add(target.val);
        while (!q.isEmpty() && K >= 0) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode curt = q.poll();
                if (K == 0) res.add(curt.val);
                if (map.get(curt) != null) {
                    for (TreeNode next : map.get(curt)) {
                        if (visited.contains(next.val)) continue;
                        visited.add(next.val);
                        q.offer(next);
                    }
                }
            }
            K--;
        }
        return res;
    }
    
    private void traverse(TreeNode curt, TreeNode parent, Map<TreeNode, Set<TreeNode>> map) {
        if (curt == null) return;
        map.putIfAbsent(curt, new HashSet<>());
        map.putIfAbsent(parent, new HashSet<>());
        if (parent != null) {
            map.get(curt).add(parent);
            map.get(parent).add(curt);
        }
        traverse(curt.left, curt, map);
        traverse(curt.right, curt, map);
    }

1145. Binary Tree Coloring Game

Count left and right children's nodes of the player 1's initial node with value x. Lets call countLeft and countRight.

count will recursively count the number of nodes, in the left and in the right. n - countLeft - countRight will be the number of nodes in the "subtree" of parent. Now we just need to compare max(left, right, parent) and n / 2

int countLeft = 0, countRight = 0;
public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
    int count = count(root, x);
    return Math.max(Math.max(countLeft, countRight), 
                    n - countLeft - countRight - 1) > n / 2;
}

private int count(TreeNode root, int x) {
    if (root == null) {
        return 0;
    }
    int L = count(root.left, x);
    int R = count(root.right, x);
    if (root.val == x) {
        countLeft = L;
        countRight = R;
    }
    return L + R + 1;
} 

671. Second Minimum Node In a Binary Tree

long res = Long.MAX_VALUE;
int min;
public int findSecondMinimumValue(TreeNode root) {
    min = root.val;
    dfs(root);
    return res == Long.MAX_VALUE ? -1 : (int)res;
}

private void dfs(TreeNode root) {
    if (root == null) return;
    if (root.val < res && root.val > min) {
        res = root.val;
    }
    dfs(root.left);
    dfs(root.right);
}