问题

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).

Have you met this question in a real interview? Yes
Example
Given binary tree {3,9,20,#,#,15,7},

return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]

分析

我们构造一个集合来存储一行的元素，然后遍历这个集合把它的孩子加入到另外一个集合中，最后注意加入结果集的是时候要加到队首。

代码

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /*
     * @param root: A tree
     * @return: buttom-up level order a list of lists of integer
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        // write your code here
        List<List<Integer>> res=new ArrayList();
        List<TreeNode> temp=new ArrayList();
        if(root!=null){
            temp.add(root);
        }
        while(!temp.isEmpty()){
            List<Integer> list=new ArrayList();
            List<TreeNode> temp2=new ArrayList();
            for(TreeNode node:temp){
                list.add(node.val);
                if(node.left!=null){
                    temp2.add(node.left);
                }
                if(node.right!=null){
                    temp2.add(node.right);
                }
            }
            temp=temp2;
            temp2=null;
            res.add(0,list);
        }
        return res;
    }
}