107.Binary-Tree-Level-Order-Traversal-II

107. Binary Tree Level Order Traversal II

题目地址

• http://www.lintcode.com/problem/binary-tree-level-order-traversal-ii/

• https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

• http://www.jiuzhang.com/solutions/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).

代码

Approach 1: Using a stack

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (root == null) return result;

    Stack<ArrayList<Integer>> s = new Stack<ArrayList<Integer>>();
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    q.offer(root);
    while (!q.isEmpty()) {
      ArrayList<Integer> level = new ArrayList<Integer>();
      for (int i = 0; i < q.szie(); i++) {
        TreeNode node = q.poll();
        level.add(node.val);
        if (node.left != null) q.offer(node.left);
        if (node.right != null) q.offer(node.right);
      }

      s.push(level);
    }

    while (!s.empty()) {
      result.add(s.pop());
    }
     // Or adopt the approch of Collections.reverse(result);

    return result;
  }
}