107. Binary Tree Level Order Traversal II (Easy)
https://leetcode.com/problems/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,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ]
Solutions
class Solution {
Map<Integer, List<Integer>> levels = new HashMap<>();
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
recurse(root, 0);
int max = 0;
for (Integer k : levels.keySet()) {
if (k > max) {
max = k;
}
}
List<List<Integer>> ans = new ArrayList<>();
for (int i = max; i >= 0; i--) {
ans.add(levels.get(i));
}
return ans;
}
private void recurse(TreeNode root, int depth) {
if (root == null) {
return;
}
if (!levels.containsKey(depth)) {
levels.put(depth, new ArrayList<Integer>());
}
levels.get(depth).add(root.val);
recurse(root.left, depth + 1);
recurse(root.right, depth + 1);
}
}