Question
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,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[ [15,7] [9,20], [3], ]
Stats
| Frequency | 1 |
| Difficulty | 3 |
| Adjusted Difficulty | 1 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is the same question as previous one.
Solution
There are also 2 solution: BFS and DFS.
I post BFS code below. Only 2 lines are different: ans.get() and ans.add().
Code
public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if (root == null) return ans;
Queue<TreeNode> q = new LinkedList<TreeNode>();
q.add(root);
while (! q.isEmpty()) {
ans.add(0, new ArrayList<Integer>());
int curSize = q.size();
for (int i = 0; i < curSize; i ++) {
TreeNode node = q.remove();
ans.get(0).add(node.val);
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
}
return ans;
}