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 1: iterative BFS
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res=new LinkedList<>();
Queue<TreeNode> q1=new LinkedList<>();
Queue<TreeNode> q2=new LinkedList<>();
if (root==null) return res;
q1.offer(root);
while (!q1.isEmpty()) {
List<Integer> one=new ArrayList<>();
while (!q1.isEmpty()) {
TreeNode x=q1.poll();
one.add(x.val);
if (x.left!=null) q2.offer(x.left);
if (x.right!=null) q2.offer(x.right);
}
res.add(0,one);
Queue<TreeNode> temp=q1;
q1=q2;
q2=temp;
}
return res;
}
}
Solution 2: Recursive DFS, compare to BFS version, the insertion of new line cost is high.
public class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
dfs(root,0,res);
return res;
}
private void dfs(TreeNode x, int d, List<List<Integer>> res) {
if (x==null) return;
if (d==res.size()) res.add(0,new ArrayList<Integer>());//cost high for ArrayList
res.get(res.size()-d-1).add(x.val);//cost low, happen more frequently
dfs(x.left,d+1,res);
dfs(x.right,d+1,res);
}
}
没有评论:
发表评论