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
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] ]
Solution:
Actually, I didn't come out a very "good" / special solution for this problem, I just simply reverse the result of level order traversal.
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
if(root==null) return res;
LinkedList<TreeNode> q=new LinkedList<TreeNode>();
q.offer(root);
int curL=0;
int lastL=1;
List<Integer> items=new ArrayList<Integer>();
while(!q.isEmpty()){
TreeNode cur=q.poll();
lastL--;
items.add(cur.val);
if(cur.left!=null){
q.offer(cur.left);
curL++;
}
if(cur.right!=null){
q.offer(cur.right);
curL++;
}
if(lastL==0){
res.add(items);
items=new ArrayList<Integer>();
lastL=curL;
curL=0;
}
}
Collections.reverse(res);
return res;
}
No comments:
Post a Comment