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

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.

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

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

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.

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.

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).

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.

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

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

### 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

**Basic Operations: preorder, inorder, postorder**

What about inorder?

- Inorder successor: Recursion/ Iterative

What about preorder?

Insert a node

compare root and inserted node，insert the node to the null pointer child.

Delete a node

Recursive : 1. Find the node

- Does the node have children? How many children?

Lowest Common Ancestor of a Binary Search Tree Recusion

inorder traversal property ??

Find Mode in Binary Search Tree sorted?

Kth Smallest Element in a BST (from small to large)

Two Sum IV – Input is a BST two pointer solution

Minimum Distance Between BST Nodes

Serialize/Deserialize

Use binary search property:

root of tree is the mid of sorted array?

Convert Sorted Array to Binary Search Tree