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

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> levelOrder(TreeNode root) {        List> result = new ArrayList>();        Queue queue = new LinkedList();        if (root == null) {            return result;        }        queue.offer(root);        while(!queue.isEmpty()) {            int size = queue.size();            List list = new LinkedList();            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

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

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

inorder traversal property ??

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