BinaryTreeLevelOrderTraversalII.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 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).
 *
 * <p>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], ] confused what "{1,#,2,3}" means? > read more on
 * how binary tree is serialized on OJ.
 */
public class BinaryTreeLevelOrderTraversalII {
  public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
    if (root == null) return ret;
    ArrayList<Integer> level = new ArrayList<Integer>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    int currentLevel = 1;
    int nextLevel = 0;
    while (!queue.isEmpty()) {
      TreeNode node = queue.remove();
      level.add(node.val);
      currentLevel--;
      if (node.left != null) {
        queue.add(node.left);
        nextLevel++;
      }
      if (node.right != null) {
        queue.add(node.right);
        nextLevel++;
      }
      if (currentLevel == 0) {
        ret.add(level);
        level = new ArrayList<Integer>();
        currentLevel = nextLevel;
        nextLevel = 0;
      }
    }
    int i = 0, j = ret.size() - 1;
    while (i < j) {
      ArrayList<Integer> tmp = ret.get(i);
      ret.set(i, ret.get(j));
      ret.set(j, tmp);
      i++;
      j--;
    }
    return ret;
  }
}