[Leetcode] Binary Tree Level Order Traversal II

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

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

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

从下往上的层次遍历，两种方法，递归或者使用stack，或者直接使用Collections.reverse()方法来把原来的结果翻转，原理和本质是一样的。

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<TreeNode> level1 = new ArrayList<TreeNode>();
        List<TreeNode> level2;
        if(root == null) return result;
        level1.add(root);
        while(level1.size() != 0) {
            level2 = new ArrayList<TreeNode>();
            List<Integer> list = new ArrayList<Integer>();
            for(TreeNode node : level1) {
                list.add(node.val);
                if(node.left != null) level2.add(node.left);
                if(node.right != null) level2.add(node.right);
            }
            result.add(list);
            level1 = level2;
        }
        Collections.reverse(result);
        return result;
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root == null) return result;
        List<TreeNode> roots = new ArrayList<TreeNode>();
        roots.add(root);
        recurse(roots, result);
        return result;
    }
    
    private void recurse(List<TreeNode> roots, List<List<Integer>> result) {
        if(roots.size() == 0) return ; // terminate condition
        List<TreeNode> children = new ArrayList<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        for(TreeNode node : roots) {
            list.add(node.val);
            if(node.left != null) children.add(node.left);
            if(node.right != null) children.add(node.right);
        }
        recurse(children, result);
        result.add(list);
    }