Binary Tree Level Order Traversal II

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]
] 

Naive Way: 这题，不就是之前那题把list的顺序倒过来吗。然后用了一个stack倒转顺序。

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

public class Solution {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> rlst = new ArrayList<List<Integer>>();

        Stack<List<Integer>> stack = new Stack<List<Integer>>();

        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        if(root==null){return rlst;}

        queue.add(root);

        map.put(root,0);

        while(!queue.isEmpty()){

            TreeNode node = queue.poll();

            int layer = map.get(node);

            List<Integer> list;

            if(rlst.size() > layer){

                list = rlst.get(layer);

            }else{

                list = new ArrayList<Integer>();

                rlst.add(list);

            }

            rlst.get(layer).add(node.val);

            if(node.left!=null){

                queue.add(node.left);

                map.put(node.left, layer+1);

            }

            if(node.right!=null){

                queue.add(node.right);

                map.put(node.right, layer+1);

            }

        }

        for(int i = 0;i < rlst.size();i++)

            stack.push(rlst.get(i));

        rlst.clear();

        while(!stack.isEmpty()){

            rlst.add(stack.pop());

        }

        return rlst;

    }

} 

Improved Way:能否直接得到倒转的list而不是得到正的再颠倒它呢。