题目描述
给定一颗二叉树，返回其层序遍历的结果。
经典解法
层序遍历（宽度优先搜索BFS）的经典实现是，借用一个队列。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
if (root != null) queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> layer = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode x = queue.poll();
layer.add(x.val);
if (x.left != null) queue.offer(x.left);
if (x.right != null) queue.offer(x.right);
}
ans.add(layer);
}
return ans;
}
}
递归实现
下面采用DFS递归来实现层序遍历
关键点在于：
- 如何保证每一层是按照从左往右 -> 前序遍历
- 如何对每一层建立对应的
List-> 递归时传入深度信息
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
dfs(root, 0, ans);
return ans;
}
private void dfs(TreeNode node, int level, List<List<Integer>> ans) {
if (node == null) return;
// 当第一次进入某一层时, ans 里没有这一层的信息
if (ans.size() == level) ans.add(new ArrayList<>());
List<Integer> layer = ans.get(level);
layer.add(node.val);
dfs(node.left, level + 1, ans);
dfs(node.right, level + 1, ans);
}
}
由于是前序遍历【根-左-右】，则会一直往左下方钻。即会先从上到下访问每一层的第一个节点。此时会把ans中每一层的List建立起来。然后每访问一个节点，先从ans中取出这一层对应的List，然后append到最后面。
假设树是一颗满二叉树，整个DFS的过程可以这样描述：
先从上到下依次访问每一层的第一个节点，然后从下到上回溯，依次访问每一层的第二个节点；然后再从上到下，依次访问每一层的第三个节点… 整个遍历的轨迹是一个蛇形
