Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree
Given binary tree
{3,9,20,#,#,15,7}
,3 / \ 9 20 / \ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]Solution 1: recursive DFS
public class Solution {
public List<List<Integer>> levelOrder(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(new ArrayList<Integer>());
res.get(d).add(x.val);
dfs(x.left,d+1,res);
dfs(x.right,d+1,res);
}
}
Solution 2: iterative BFS
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res=new ArrayList<>();
if (root==null) return res;
Queue<TreeNode> q1=new LinkedList<>();
Queue<TreeNode> q2=new LinkedList<>();
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(one);
q1=q2;
q2=new LinkedList<>();
}
return res;
}
}
没有评论:
发表评论