[LeetCode] 107. Binary Tree Level Order Traversal II

Posted on | In

Problem

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

1
2
3
4
5
    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

1
2
3
4
5
[
  [15,7],
  [9,20],
  [3]
]

Explanation

  1. Similar to 102. Binary Tree Level Order Traversal. This time, instead of adding the sublist to the end of the result list, we should add the sublist at the beginning of the result list.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            for (int i = queue.size()-1; i >= 0; i--) {
                TreeNode popNode = queue.poll();
                temp.add(popNode.val);
                if (popNode.left != null) queue.offer(popNode.left);
                if (popNode.right != null) queue.offer(popNode.right);
            }
            res.add(0, temp);
        }

        return res;
    }
}