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

confused what `"{1,#,2,3}"`

means? > read more on how binary tree is serialized on OJ.

public class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> result = new LinkedList<List<Integer>>(); if (root == null) { return result; } List<TreeNode> currLevel = new LinkedList<TreeNode>(); currLevel.add(root); while (currLevel.size() > 0) { result.add(0, new LinkedList<Integer>()); List<TreeNode> nextLevel = new LinkedList<TreeNode>(); while (currLevel.size() > 0) { TreeNode runner = currLevel.remove(0); result.get(0).add(runner.val); if (runner.left != null) { nextLevel.add(runner.left); } if (runner.right != null) { nextLevel.add(runner.right); } } currLevel = nextLevel; } return result; } }