title: Binary Tree Level Order Traversal II
tags:
- binary-tree-level-order-traversal-ii
- No.107
- simple
- tree
- breadth-first-search
- queue

Description

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,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

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

Corner Cases

• empty root

Solutions

Queue

Insert in head for the returned list. Use number counter to divide the layers. It's obvious that the running time is O(V) when the queue operations are all in O(1).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        Queue<TreeNode>     que  = new LinkedList<TreeNode>();
        List<List<Integer>> llst = new LinkedList<List<Integer>>();
        
        if (root == null) {return llst;}
        que.offer(root);
        int curr = 0;
        int nlay = 1;

        while (!que.isEmpty()) {
            nlay = que.size();
            curr = 0;
            List<Integer> a = new LinkedList<Integer>();
            while(curr < nlay) {
                TreeNode x = que.poll();
                if (x.left  != null) {que.offer(x.left);}
                if (x.right != null) {que.offer(x.right);}
                a.add(x.val);
                curr = curr + 1;
            }
            llst.add(0, a);
        }
        return llst;
    }
}