Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

根据题目的意思进行递归操作，递归N次。有时候在整个循环结束时，记得检查下，最后一些case有没有加进结果里。

public class Solution {
    public String countAndSay(int n) {
        if (n < 1) {
            return "";
        }
        
        return countHelp("1", n - 1);
    }
    
    private String countHelp(String s, int num) {
        if (num == 0) {
            return s;
        }
        
        StringBuilder res = new StringBuilder();
        char cur = s.charAt(0);
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (cur == s.charAt(i)) {
                count++;
            } else {
                res.append(count);
                res.append(cur);
                cur = s.charAt(i);
                count = 1;
            }
        }
        res.append(count);
        res.append(cur);
        return countHelp(res.toString(), num - 1);
    }
}

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

递归，记录左右括号还剩几个，同时检测当前是否合法

public class Solution {
    //Time: O(2^n)  
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> res = new ArrayList<String>();
        generate("", n, n, res);
        return res;
    }
    
    private void generate(String cur, int left, int right, ArrayList<String> res) {
        if (left > right || left < 0 || right < 0) {
            return;
        }
        
        if (left == 0 && right == 0) {
            res.add(cur);
            return;
        }
        
        generate(cur + "(", left - 1, right, res);
        generate(cur + ")", left, right - 1, 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);
    }
}

N-Queens I && II

Given an integer n, return all distinct solutions to the n-queens puzzle.

DFS:

public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> res = new ArrayList<String[]>();
        int[] rows = new int[n];
        solve(res, rows, 0);
        return res;
    }
    
    private void solve(ArrayList<String[]> res, int[] rows, int row) {
        if (row == rows.length) {
            String[] tmp = new String[rows.length];
            draw(rows, tmp);
            res.add(tmp);
            return;
        }
        
        for (int i = 0; i < rows.length; i++) {
            rows[row] = i;
            if (valid(rows, row)) {
                solve(res, rows, row + 1);
            }
        }
    }
    
    private boolean valid(int[] rows, int row) {
        for (int i = 0; i < row; i++) {
            if (rows[i] == rows[row]) {
                return false;
            }
            
            if (Math.abs(rows[row] - rows[i]) == Math.abs(row - i)) {
                return false;
            }
        }
        return true;
    }
    
    private void draw(int[] rows, String[] tmp) {
        for (int i = 0; i < tmp.length; i++) {
            StringBuilder cur = new StringBuilder();
            int pos = rows[i];
            for (int j = 0; j < pos; j++) {
                cur.append('.');
            }
            cur.append('Q');
            for (int j = pos + 1; j < tmp.length; j++) {
                cur.append('.');
            }
            tmp[i] = cur.toString();
        }
    }
}

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

经典的递归问题。用一个cols[]数组，cols[i]: i代表第几列，cols[i]代表在第i列的行数。同时还要检查在当前列当前行和之前比较是否合法。

public class Solution {
    //Time: O(n^n)  Space: O(n)
    private int num = 0;
    public int totalNQueens(int n) {
        int[] cols = new int[n];
        Nqueen(cols, 0);
        return num;
    }
    
    private void Nqueen(int[] cols, int col) {
        if (col == cols.length) {
            num++;
            return;
        }
        
        for (int i = 0; i < cols.length; i++) {
            cols[col] = i;
            if (valid(cols, col)) {
                Nqueen(cols, col + 1);
            }
        }
    }
    
    private boolean valid(int[] cols, int col) {
        for (int i = 0; i < col; i++) {
            if (cols[i] == cols[col]) {
                return false;
            }
            if (Math.abs(cols[col] - cols[i]) == Math.abs(col - i)) {
                return false;
            }
        }
        return true;
    }
}

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;
    }
}

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