4. 树和递归

1. 树

1.1 二叉树前序

• 递归

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        resultList.add(root.val);
        if (root.left != null) {
            resultList.addAll(preorderTraversal(root.left));
        }
        if (root.right != null) {
            resultList.addAll(preorderTraversal(root.right));
        }
        return resultList;
    }

• 栈

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<Integer>();
        if (root == null) {
            return resultList;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                resultList.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return resultList;
    }

  1.2 二叉树中序

• 递归

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        if (root.left != null) {
            resultList.addAll(preorderTraversal(root.left));
        }
        resultList.add(root.val);
        if (root.right != null) {
            resultList.addAll(preorderTraversal(root.right));
        }
        return resultList;
    }

• 栈

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            resultList.add(root.val);
            root = root.right;
        }
        return resultList;
    }

  1.3 二叉树后序

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        if (root.left != null) {
            resultList.addAll(preorderTraversal(root.left));
        }
        if (root.right != null) {
            resultList.addAll(preorderTraversal(root.right));
        }
        resultList.add(root.val);
        return resultList;
    }

• 栈 ```java

  public List postorderTraversal(TreeNode root) {

    List<Integer> resultList = new ArrayList<Integer>();
    if (root == null) {
        return resultList;
    }
    Deque<TreeNode> stack = new LinkedList<TreeNode>();
    TreeNode prev = null;
    while (root != null || !stack.isEmpty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        if (root.right == null || root.right == prev) {
            resultList.add(root.val);
            prev = root;
            root = null;
        } else {
            stack.push(root);
            root = root.right;
        }
    }
    return resultList;

  }

<a name="SKCie"></a>
### 1.4 N叉树前序
```java
    public List<Integer> preorder(Node root) {
        List<Integer> resultList = new ArrayList<>();
        if (null == root) {
            return resultList;
        }
        resultList.add(root.val);
        if (null != root.children && root.children.size() > 0) {
            for (Node temp : root.children) {
                resultList.addAll(preorder(temp));
            }
        }
        return resultList;
    }

1.5 N叉树后序

    public List<Integer> preorder(Node root) {
        List<Integer> resultList = new ArrayList<>();
        if (null == root) {
            return resultList;
        }
        if (null != root.children && root.children.size() > 0) {
            for (Node temp : root.children) {
                resultList.addAll(preorder(temp));
            }
        }
        resultList.add(root.val);
        return resultList;
    }

1.6 N叉树层次遍历

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> resultList = new ArrayList<>();
        if (root == null) {
            return resultList;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                level.add(node.val);
                queue.addAll(node.children);
            }
            resultList.add(level);
        }
        return resultList;
    }

1.7 从前序与中序遍历序列构造二叉树（105）

1.8 路径总和 II （113）

2. 递归

2.0 递归模版

    public void recursion(int level, Object params) {
        // 递归终止
        if (level > MAX_LEVEL) {
            // proccess result...
            return;
        }
        // do some work.
        process(level, params);
        // recursion
        recursion(level, newParams);
        // if needed, update status.
    }

2.1 爬楼梯（70）

• 解法1: 递归分解子问题

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        return climbStairs( n - 1 ) + climbStairs( n - 2 );
    }

• 记录前两个值：类似于斐波那契饿数列

    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int a =1 ,b =2 ,c = 3;
        for (int i = 3; i <= n; i++) {
            c =  a + b;
            a = b;
            b = c; 
        }
        return c;
    }

  2.2 括号生成（22）

    public List<String> generateParenthesis(int n) {
        List<String> resultList = new ArrayList<>();
        recursion(0, 0, n, "", resultList);
        return resultList;
    }
    private void recursion(int left, int right, int n, String s, List<String> resultList) {
        if (left == n && left == right) {
            resultList.add(s);
            return;
        }
        if (left < n) {
            recursion(left + 1, right, n, s + "(", resultList);
        }
        if (right < left) {
            recursion(left, right + 1, n, s + ")", resultList);
        }
    }