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

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

return its bottom-up level order traversal as:

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

Solution:

  1. /**
  2. * Definition for binary tree
  3. * public class TreeNode {
  4. * int val;
  5. * TreeNode left;
  6. * TreeNode right;
  7. * TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Solution {
  11. public List<List<Integer>> levelOrderBottom(TreeNode root) {
  12. List<List<Integer>> res = new ArrayList<List<Integer>>();
  13. List<Integer> list = new ArrayList<Integer>();
  14. if (root == null) {
  15. return res;
  16. }
  17. Queue<TreeNode> curr = new LinkedList<TreeNode>();
  18. Queue<TreeNode> next = new LinkedList<TreeNode>();
  19. curr.add(root);
  20. while (!curr.isEmpty()) {
  21. TreeNode node = curr.poll();
  22. list.add(node.val);
  23. if (node.left != null) {
  24. next.add(node.left);
  25. }
  26. if (node.right != null) {
  27. next.add(node.right);
  28. }
  29. if (curr.isEmpty()) {
  30. res.add(0, list);
  31. list = new ArrayList<Integer>();
  32. curr = next;
  33. next = new LinkedList<TreeNode>();
  34. }
  35. }
  36. return res;
  37. }
  38. }