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:

 

  1. Top Down

 

  1. 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);
}

 

  1. Bottom Up

 

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

  1. Path Sum I for each node , N * log(N)
  2. 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?

 

  1. The value in each node must be greater than (or equal to) any values stored in its left subtree.
  2. 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

 

Basic Operations: preorder, inorder, postorder

What about inorder?

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

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

Convert BST to Greater Tree

 

Serialize/Deserialize

 

Use binary search property:

root of tree is the mid of sorted array?

 

Convert Sorted Array to Binary Search Tree

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s