Contents
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,null,null,15,7]
,
3 / \ 9 20 / \ 15 7
return its bottom-up level order traversal as:
[ [15,7], [9,20], [3] ]
Solution
class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> rlist = new LinkedList<>(); if (root == null) return rlist; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> ilist = new LinkedList<>(); for (int i = 0; i < size; i++) { TreeNode curNode = queue.remove(); ilist.add(curNode.val); if (curNode.left != null) { queue.add(curNode.left); } if (curNode.right != null) { queue.add(curNode.right); } } rlist.add(ilist); } Collections.reverse(rlist); return rlist; } }
Execution time: 3 ms , defeated in all Java commits 65.43% User
Memory consumption: 35.2 MB , defeated in all Java commits 94.34% User