Leetcode Tree Summary

Binary Tree

Traversal： preorder, inorder, post order

recursion template：

def traversal(root):
# none or leaf
if not root:
# do sth

# divide
left = traversal(root.left)
right = traversal(root.right)

# Conquer
res = # merge
return res

iterative template：

Details see:

https://www.jianshu.com/p/456af5480cee

preorder example:

postorder

Recursion Type:

Top Down

return specific value for null node
2. update the answer if needed                      // anwer <– params
3. left_ans = top_down(root.left, left_params)      // left_params <– root.val, params
4. right_ans = top_down(root.right, right_params)   // right_params <– root.val, params
5. return the answer if needed                      // answer <– left_ans, right_ans

It is like preorder

take maximum depth of tree as example:

private int answer; // don’t forget to initialize answer before call maximum_depth
private void maximum_depth(TreeNode root, int depth) {
   if (root == null) {
       return;
   }
   if (root.left == null && root.right == null) {
       answer = Math.max(answer, depth);
   }
   maximum_depth(root.left, depth + 1);
   maximum_depth(root.right, depth + 1);
}

Bottom Up

return specific value for null node
2. left_ans = bottom_up(root.left)          // call function recursively for left child
3. right_ans = bottom_up(root.right)        // call function recursively for right child
4. return answers                           // answer <– left_ans, right_ans, root.val

It is like postorder

public int maximum_depth(TreeNode root) {
if (root == null) {
return 0; // return 0 for null node
}
int left_depth = maximum_depth(root.left);
int right_depth = maximum_depth(root.right);
return Math.max(left_depth, right_depth) + 1; // return depth of the subtree rooted at root
}

Basic Recursion problems:

Maximum Depth of Binary Tree – easy

Minimum Depth of Binary Tree – easy

Invert Binary Tree – easy

Same Tree – easy

Symmetric Tree – easy

Merge Two Binary Trees – easy

Path/Path Sum Series:

Binary Tree Paths : top down, pass in a path

Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Path Sum 1 + use list to add valid paths

Path Sum III

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

Path Sum I for each node , N * log(N)
Use prefix sum, one pass. Need a hashmap

Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Longest Univalue Path

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.

Diameter of Binary Tree

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

BFS

level order traversal

public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> result = new ArrayList<List<Integer>>();
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       if (root == null) {
           return result;
       }
       queue.offer(root);
       while(!queue.isEmpty()) {
           int size = queue.size();
           List<Integer> list = new LinkedList<Integer>();
           for (int i = 0; i < size; i++) {
               TreeNode node = queue.poll();
               list.add(node.val);
               if (node.left != null) {
                   queue.offer(node.left);
               }
               if (node.right != null) {
                   queue.offer(node.right);
               }
           }
           result.add(list);
       }
       return result;
   }

Binary Tree Level Order Traversal

Binary Tree Zigzag Level Order Traversal – medium

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

Find Bottom Left Tree Value

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

Average of Levels in Binary Tree

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Find Largest Value in Each Tree Row

You need to find the largest value in each row of a binary tree.

Maximum Width of Binary Tree

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

Use count: the position index of each node in binary tree

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes’ values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Use count to record position index

Find Bottom Left Tree Value

Binary Search Tree

Definition: Why call it “Binary Search” tree?

The value in each node must be greater than (or equal to) any values stored in its left subtree.
The value in each node must be less than (or equal to) any values stored in its right subtree.

In most leetcode problems, no equal value nodes

Validate Binary Search Tree : Recursion, keep min and max
Binary Search Tree Iterator : next()? use a stack
Closest Binary Search Tree Value
Closest Binary Search Tree Value II now return k cloest values answer: maintain an ordered list