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], ]
public class Solution { public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) { // Start typing your Java solution below // DO NOT write main() function ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); Stack<ArrayList<Integer>> stack = new Stack<ArrayList<Integer>>(); ArrayList<TreeNode> current = new ArrayList<TreeNode>(); if(root != null) current.add(root); while(!current.isEmpty()){ ArrayList<TreeNode> nextlevel = new ArrayList<TreeNode>(); ArrayList<Integer> list = new ArrayList<Integer>(); for(TreeNode n:current){ list.add(n.val); if(n.left != null) nextlevel.add(n.left); if( n.right != null) nextlevel.add(n.right); } current = nextlevel; stack.push(list); } while(!stack.isEmpty()){ result.add(stack.pop()); } return result; } }