CC150: Tree to LinkedList

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists).

第一眼感觉就是level by level，用BFS就行了。

但是实际可以用类似一直pre-order的顺序遍历，但是我们需要一个额外的变量level，来记录当前点是对应第几层的。
No BFS version

public class Solution {
    public ArrayList<LinkedList<TreeNode>> create(TreeNode root) {
     ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();
     createHelp(root, lists, 0);
     return lists;
    }

    private void createHelp(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, int level) {
     if (root == null) {
      return;
     }

     if (lists.size() == level) {
      //for current level, we didn't create a new list
      LinkedList<TreeNode> list = new LinkedList<TreeNode>();
      list.add(root);
      lists.add(list);
     } else {
      LinkedList<TreeNode> list = lists.get(level);
      list.add(root);
     }

     createHelp(root.left, lists, level + 1);
     createHelp(root.right, lists, level + 1);
    }

    public ArrayList<LinkedList<TreeNode>> create(TreeNode root) {
     ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();
     if (root == null) {
      return lists;
     }
 
     Queue<TreeNode> queue = new LinkedList<TreeNode>();
     queue.offer(root);
     while(!queue.isEmpty()) {
      int size = queue.size();
      LinkedList<TreeNode> list = new LinkedList<TreeNode>();
      for (int i = 0; i < size; i++) {
       TreeNode cur = queue.poll();
       if (cur.left != null) {
        queue.offer(cur.left);
       }
       if (cur.right != null) {
        queue.offer(cur.right);
       }
       list.add(cur);
      }
      lists.add(list);
     }
     return lists;
    }
}

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

两个node互换。举个例子，tree inorder：1，2，3，4，5，6，7

有可能会有1对降序：1，2，4，3，5，6，7。也有可能会有两对降序：1，6，3，4，5，2，7

但是无论如何，第一次降序的大的和最后一次降序小的就是对调的两个。

public class Solution {
    //Time: O(n)
    private TreeNode first = null;
    private TreeNode second = null;
    private TreeNode last = null;
    private void find(TreeNode root) {
        if (root == null) {
            return;
        }
        
        find(root.left);
        if (last != null && first == null && last.val > root.val) {
            first = last;
        }
        if (last != null && first != null && last.val > root.val) {
            second = root;
        }
        last = root;
        find(root.right);
    }
    
    public void recoverTree(TreeNode root) {
        find(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

设置一个最大和最小值，同时更新。

 public class Solution {
    //Time: O(n)
    public boolean isValidBST(TreeNode root) {
        return isValid(root, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }
    
    private boolean isValid(TreeNode root, int max, int min) {
        if (root == null) {
            return true;
        }
        
        if (root.val >= max || root.val <= min) {
            return false;
        }
        return isValid(root.left, root.val, min) && isValid(root.right, max, root.val);
    }
}

用类似一个inorder的方法，灵感来自recover BST。

public class Solution {
    private TreeNode last = null;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        boolean left = isValidBST(root.left);
        if (last != null && last.val >= root.val) {
            return false;
        }
        last = root;
        boolean right = isValidBST(root.right);
        return left && right;
    }
}

Construct Binary Tree from Preorder and Inorder Traversal && Inorder and Postorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

可以利用preorder的第一个肯定是root的性质，同时找到此点在inorder中对应的位置，从而把这两个数组对应分割成左子树和右子树。

update: 在搜索Positions时可以用二分法，这样最坏Time: O(nlogn)

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    private TreeNode build(int[] preorder, int prestart, int preend, 
                           int[] inorder, int instart, int inend) {
        if (preend < prestart || inend < instart) {
            return null;
        }               
        
        TreeNode root = new TreeNode(preorder[prestart]);
        int position = 0;
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == preorder[prestart]) {
                position = i;
            }
        }
        
        root.left = build(preorder, prestart + 1, prestart + position - instart,
                          inorder, instart, position - 1);
        root.right = build(preorder, prestart + position - instart + 1, preend,
                           inorder, position + 1, inend);
        return root;
    }
}

Given inorder and postorder traversal of a tree, construct the binary tree.

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    
    private TreeNode build(int[] inorder, int instart, int inend,
                           int[] postorder, int poststart, int postend) {
        if (inend < instart || postend < poststart) {
            return null;
        }               
        
        TreeNode root = new TreeNode(postorder[postend]);
        int position = 0;
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == postorder[postend]) {
                position = i;
            }
        }
        
        root.left = build(inorder, instart, position - 1, 
                          postorder, poststart, poststart + position - instart - 1);
        root.right = build(inorder, position + 1, inend, 
                           postorder, poststart + position - instart, postend - 1);
        return root;
    }
}

Binary Tree Zigzag 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).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3

   / \

  9  20

     /    \

   15   7

return its zigzag level order traversal as:

[

  [3],

  [20,9],

  [15,7]

]

BFS: 用两个stack来实现层遍历

public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> cur = new Stack<TreeNode>();
        Stack<TreeNode> next = new Stack<TreeNode>();
        cur.push(root);
        boolean reverse = true;
        
        while (!cur.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            while (!cur.isEmpty()) {
                TreeNode node = cur.pop();
                if (reverse) {
                    if (node.left != null) {
                        next.push(node.left);
                    }
                    if (node.right != null) {
                        next.push(node.right);
                    }
                } else {
                    if (node.right != null) {
                        next.push(node.right);
                    }
                    if (node.left != null) {
                        next.push(node.left);
                    }
                }
                level.add(node.val);
            }
            reverse = !reverse;
            Stack<TreeNode> temp = cur;
            cur = next;
            next = temp;
            res.add(level);
        }
        return res;
    }
}

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

每次二分法找中点，此点为root，左半部分为左子树，右半部分为右子树。

public class Solution {
    //Time: O(nlogn)
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        
        if (head.next == null || head.next.next == null) {
            TreeNode root = new TreeNode(head.val);
            if (head.next != null) {
                root.right = new TreeNode(head.next.val);
            }
            return root;
        }
        
        ListNode midPre = findMidPre(head);
        ListNode mid = midPre.next;
        TreeNode root = new TreeNode(mid.val);
        midPre.next = null;
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(mid.next);
        return root;
    }
    
    private ListNode findMidPre(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1

        /  \

       2   5

      /  \    \

     3   4   6

The flattened tree should look like:

   1

    \

     2

       \

        3

          \

           4

             \

              5

                \

                 6

把Tree变成LinkedList，我们需要一个额外的变量记录上一次变化到那个点，这样对于当前点，我们才能将它连接到上一个点。

public class Solution {
    //Time: O(n)
    private TreeNode last = null;
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        
        if (last != null) {
            last.left = null;
            last.right = root;
        }
        
        last = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
    }
}

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

DFS:

public class Solution {
    //Time: O(n)
    int min = Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        getMin(root, 1);
        return min;
    }
    
    private void getMin(TreeNode root, int depth) {
        if (root.left == null && root.right == null) {
            min = Math.min(min, depth);
        }
        
        if (root.left != null) {
            getMin(root.left, depth + 1);
        }
        if (root.right != null) {
            getMin(root.right, depth + 1);
        }
    }
}

BFS:

public class Solution {
    //Time: O(n)
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int length = 1;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                if (cur.left == null && cur.right == null) {
                    return length;
                }
            }
            length++;
        }
        return length;
    }
}

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1

   /  \

  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

DFS: 

public class Solution {
    //Time: O(n)
    private int sum = 0;
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return sum;
        }
        getSum(root, 0);
        return sum;
    }
    
    private void getSum(TreeNode root, int cur) {
        cur = cur * 10 + root.val;
        if (root.left == null && root.right == null) {
            sum += cur;
            return;
        }
        if (root.left != null) {
            getSum(root.left, cur);
        }
        if (root.right != null) {
            getSum(root.right, cur);
        }
    }
}

BFS: 

public class Solution {
    //Time: O(n)
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int sum = 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> queuesum = new LinkedList<Integer>();
        queue.offer(root);
        queuesum.offer(root.val);
        
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int cursum = queuesum.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
                queuesum.offer(cursum * 10 + cur.left.val);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                queuesum.offer(cursum * 10 + cur.right.val);
            }
            if (cur.left == null && cur.right == null) {
                sum += cursum;
            }
        }
        return sum;
    }
}

Path Sum I && II

I: 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.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

DFS: 

public class Solution {
    //Time: O(n)
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        return checkPath(root, root.val, sum);
    }
    
    private boolean checkPath(TreeNode root, int cur, int sum) {
        if (root.left == null && root.right == null) {
            if (cur == sum) {
                return true;
            }
            return false;
        }
        
        boolean left = false;
        boolean right = false;;
        if (root.left != null) {
            left = checkPath(root.left, cur + root.left.val, sum);
        }
        if (root.right != null) {
            right = checkPath(root.right, cur + root.right.val, sum);
        }
        return left || right;
    }
}

BFS: 

public class Solution {
    //Time: O(n)
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queue.offer(root);
        queueSum.offer(root.val);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            int cursum = queueSum.poll();
            if (cur.left != null) {
                queue.offer(cur.left);
                queueSum.offer(cursum + cur.left.val);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
                queueSum.offer(cursum + cur.right.val);
            }
            if (cur.left == null && cur.right == null && cursum == sum) {
                return true;
            }
        }
        return false;
    }
}

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

DFS: 

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

Binary Tree Level Order Traversal I && II

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

用一个queue进行BFS。第二个只需把25行改成add(0, level)

public class Solution {
    //Time: O(n)  Space: O(n)
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return res;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> level = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                level.add(cur.val);
                
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric: 

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

public class Solution {
    //Time: O(n)
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return check(root.left, root.right);
    }
    
    private boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }
        if (left == null || right == null) {
            return false;
        }
        if (left.val != right.val) {
            return false;
        }
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

这道题比较直观的解法对于每个点的左右子树都用Maximum Depth of Binary Tree的方法求解并进行合法检查。但这样会有很多重复的操作。
递归的求解左右子树的深度，看是否符合平衡要求。

public class Solution {
    //Time: O(n)  Space: O() depends on the structure of tree
    public boolean isBalanced(TreeNode root) {
        return checkBalance(root) != -1;
    }
    
    private int checkBalance(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = checkBalance(root.left);
        int right = checkBalance(root.right);
        if (left == - 1 || right == -1) {
            return -1;
        }
        
        return Math.abs(left - right) <= 1 ? 1 + Math.max(left,right) : -1;
    }
}

Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

对排好序的数组二分，中点就是root，左边部分左子树，右边部分右子树

public class Solution {
    //Time: O(n)  
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0) {
            return null;
        }
        return convert(num, 0, num.length - 1);
    }
    
    private TreeNode convert(int[] num, int start, int end) {
        if (start > end) {
            return null;
        }
        
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = convert(num, start, mid - 1);
        root.right = convert(num, mid + 1, end);
        return root;
    }
}

Populating Next Right Pointers in Each Node I & II

I : Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.  Initially, all next pointers are set to NULL.
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

可以用一个queue做BFS，但是此题要求Space: O(n)。因为这个是个完全树，所以当前左子树的下一个肯定是当前右子树，当前右子树肯定是当前下一个的左子树。注意Null check。

public class Solution {
    //Time: O(n)  Space: O(logn)
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            root.left.next = root.right;   
        }
        if (root.right != null) {
            root.right.next = root.next == null ? null : root.next.left;   
        }
        connect(root.left);
        connect(root.right);
    }
}

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

比上一题复杂不少，但是基本思路还是一样的。当前点有两个子树时，关键在于右子树的下一个，当前点只有一个子树时，关键在于这个子树对应的下一个。

首先要坚持当前点是否有下一个，如果有在检查下一个点是否有左右子树，把之前的那个子树对应到现在的的子树。递归对整棵树求解，需要注意的是先对右子树递归。

public class Solution {
    //Time: O(n)  
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }
        
        TreeLinkNode p = null;
        if (root.left != null && root.right != null) {
            root.left.next = root.right;
            p = root.right;
        } else if (root.left != null || root.right != null) {
            p = root.left != null ? root.left : root.right;
        } else {
            return;
        }
        TreeLinkNode p2 = root;
        while (p2.next != null && p2.next.left == null && p2.next.right == null) {
            p2 = p2.next;
        }
        p.next = p2.next == null ? null : (p2.next.left != null ? p2.next.left : p2.next.right);
        connect(root.right);
        connect(root.left);
    }
}

Binary Tree Inorder/Preorder/Postorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1

    \

     2

    /

   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

Recursion:

public class Solution {
    //Time: O(n)  Space: O(depth of tree)
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
    
    private void inorder(TreeNode root, ArrayList<Integer> res) {
        if (root == null) {
            return;
        }
        //res.add(root.val);  pre
        inorder(root.left, res);
        //res.add(root.val);  in
        inorder(root.right, res);
        //res.add(root.val);  post
    }
}

Iterative: Inorder
使用一个stack，如果有左子树，就把当前点放进stack，反之pop出一个node，检查它的右子树。

public class Solution {
    //Time: O(n)  Space: O(depth of tree)
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        while (!stack.isEmpty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                p = stack.pop();
                res.add(p.val);
                p = p.right;
            }
        }
        return res;
    }
}

Iterative: Preorder
用一个stack，当前node被pop出后，先push右子树节点，再push左子树节点

public class Solution {
    //Time: O(n)  Space: O(n)
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.right != null) { //push right first
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
            res.add(cur.val);
        }
        return res;
    }
}

Iterative: Postorder

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (root == null) {
            return res;
        }
        
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode pre = null;
        TreeNode cur = root;
        stack.push(root);
        while (!stack.isEmpty()) {
            cur = stack.peek();
            if (pre == null || pre.left == cur || pre.right == cur) {
                if (cur.left != null) {
                    stack.push(cur.left);
                } else if (cur.right != null) {
                    stack.push(cur.right);
                }
            } else if (cur.left == pre) {
                if (cur.right != null) {
                    stack.push(cur.right);
                }
            } else {
                res.add(cur.val);
                stack.pop();
            }
            pre = cur;
        }
        return res;
    }
}

Unique Binary Search Trees I && II

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

比较巧妙的思路，假设我们有n个点，我们取i作为root，那左子树就是1到i - 1个点组成的情况，右子树就是i + 1到n组成的情况。把每个点作为root的情况进行累加，所以当我们知道1，2...n个点的组成树的种类，我们也能知道n + 1个点组成树的种类。

public class Solution {
    //Time: O(n^2)  Space: O(n)
    public int numTrees(int n) {
        int[] map = new int[n + 1];
        map[0] = map[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                map[i] += map[j - 1] * map[i - j];
            }
        }
        return map[n];
    }
}

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
  return generate(1, n);
    }
    
    private ArrayList<TreeNode> generate(int start, int end) {
        ArrayList<TreeNode> bst = new ArrayList<TreeNode>();
        if (start > end) {
            bst.add(null);
            return bst;
        }
        
        for (int i = start; i <= end; i++) {
            ArrayList<TreeNode> left = generate(start, i - 1);
            ArrayList<TreeNode> right = generate(i + 1, end);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode root = new TreeNode(i);
                    root.left = left.get(j);
                    root.right = right.get(k);
                    bst.add(root);
                }
            }
        }
        return bst;
    }
}

Same Tree

Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

同样还是对左右子树求递归，很多树的题目都可以用对子树递归来求解。需要注意的是，递归的空间复杂度就是递归的深度也就是树的深度。

public class Solution {
    //Time: O(n)  Space: O(depth of tree);
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

直接用递归，求解左右子树的深度，求最大

public class Solution {
    //Time: O(n) Space: O(depth of tree);
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}