107. Binary Tree Level Order Traversal II
Easy
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]
]
package leetcode.easy; /**
* Definition for a binary tree node. public class TreeNode { int val; TreeNode
* left; TreeNode right; TreeNode(int x) { val = x; } }
*/
public class BinaryTreeLevelOrderTraversalII {
// DFS solution:
public java.util.List<java.util.List<Integer>> levelOrderBottom1(TreeNode root) {
java.util.List<java.util.List<Integer>> wrapList = new java.util.LinkedList<java.util.List<Integer>>();
levelMaker(wrapList, root, 0);
return wrapList;
} private static void levelMaker(java.util.List<java.util.List<Integer>> list, TreeNode root, int level) {
if (root == null) {
return;
}
if (level >= list.size()) {
list.add(0, new java.util.LinkedList<Integer>());
}
levelMaker(list, root.left, level + 1);
levelMaker(list, root.right, level + 1);
list.get(list.size() - level - 1).add(root.val);
} // BFS solution:
public java.util.List<java.util.List<Integer>> levelOrderBottom2(TreeNode root) {
java.util.Queue<TreeNode> queue = new java.util.LinkedList<TreeNode>();
java.util.List<java.util.List<Integer>> wrapList = new java.util.LinkedList<java.util.List<Integer>>();
if (root == null) {
return wrapList;
}
queue.offer(root);
while (!queue.isEmpty()) {
int levelNum = queue.size();
java.util.List<Integer> subList = new java.util.LinkedList<Integer>();
for (int i = 0; i < levelNum; i++) {
if (queue.peek().left != null) {
queue.offer(queue.peek().left);
}
if (queue.peek().right != null) {
queue.offer(queue.peek().right);
}
subList.add(queue.poll().val);
}
wrapList.add(0, subList);
}
return wrapList;
} @org.junit.Test
public void test() {
TreeNode tn11 = new TreeNode(3);
TreeNode tn21 = new TreeNode(9);
TreeNode tn22 = new TreeNode(20);
TreeNode tn33 = new TreeNode(15);
TreeNode tn34 = new TreeNode(7);
tn11.left = tn21;
tn11.right = tn22;
tn21.left = null;
tn21.right = null;
tn22.left = tn33;
tn22.right = tn34;
tn33.left = null;
tn33.right = null;
tn34.left = null;
tn34.right = null;
System.out.println(levelOrderBottom1(tn11));
System.out.println(levelOrderBottom2(tn11));
}
}