今天我们介绍二叉树的BFS和DFS。以前二叉树专题的时候已经使用BFS和DFS算法去解决过二叉树的相关问题。这次我们再总结一下BFS和DFS算法的特点和模板。
因为BFS算法的特点，在解决二叉树按层级遍历问题时非常有用。
我们将使用一个队列(Queue)来跟踪的所有节点级别之前我们跳到下一个级别。这也意味着,算法的空间复杂度是O (N),其中N是节点在每一层级的最大数量。
下面我们直接看题目:
https://leetcode.com/problems/binary-tree-level-order-traversal/
BFS算法流程:
因为我们每次遍历时，都是访问该节点下一层级的所有子节点，所以我们需要一个队列Queue去保存每一层的所有节点。这样算法的步骤为：
- 将根节点root放到queue中去；
- 反复访问queue直到队列为空；
- 每一次遍历时，先计算该层级的节点数量，使用循环遍历该层级的每一个节点；
- 每一次层级遍历时，从队列中出列一个节点，将它的值保存到array中去(做相关的business log的操作)；
- 访问步骤4中出队列的节点的左、右子树，分别将他们放在队列中；
- 如果队列queue不为空，重复3开始下一层级的遍历。
对应代码如下：
public List<List<Integer>> levelOrder(TreeNode root) {
// iteration 解决方法，采用队列每次存储每一层的节点，再依次遍历
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res; // 当输入为[]时候，返回不是null而是 []
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
List<Integer> subRes = new ArrayList<>(); // 该层的子结果
int num = q.size(); // 该层的节点数量
for(int i = 0; i < num; i++) {
TreeNode curr = q.poll();
subRes.add(curr.val);
if (curr.left != null) {
q.offer(curr.left);
} if (curr.right != null) { // 此时不能是else if
q.offer(curr.right);
}
}
res.add(subRes);
}
return res;
}
https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
唯一的不同就是返回的结果是逆序，从最底层开始，到最上面的root节点，那么只需要add结果的时候，insert从0开始就行。
代码如下：
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int num = q.size();
List<Integer> subRes = new ArrayList<>();
for (int i = 0; i < num; i++) {
TreeNode curr = q.poll();
subRes.add(curr.val);
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
res.add(0, subRes);
}
return res;
}
https://leetcode.com/problems/average-of-levels-in-binary-tree/
还有这个题，计算每个节点的平均数。很简单，在每一层计算一下平均数再保存结果就行了。
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int num = q.size();
double subRes = 0.0;
for (int i = 0; i < num; i++) {
TreeNode curr = q.poll();
subRes += curr.val;
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
res.add(subRes / num); // 除于每一级节点数量，计算平均数
}
return res;
}
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
这道题要zigzag访问二叉树，那么相当于每层级需要一个标志，上一层是zig访问，下一层就是zag，所以就需要加一个flag就行了，别的都是一样的。代码如下：
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res; // 当输入为[]时候，返回不是null而是 []
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
boolean isZigzag = false; // 是否是zigzag，是的话就是从右向左遍历，否则就是左向右
while(!q.isEmpty()) {
List<Integer> subRes = new ArrayList<>(); // 该层的结果
int num = q.size(); // 该层的节点数量(1 0r 2)
for(int i = 0; i < num; i++) {
TreeNode curr = q.poll();
if(isZigzag) { // 是zigzag，则插入到前面
subRes.add(0, curr.val);
} else {
subRes.add(curr.val);
}
if (curr.left != null ) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
isZigzag = !isZigzag;
res.add(subRes);
}
return res;
}
https://leetcode.com/problems/maximum-depth-of-binary-tree/
使用BFS解决这个题，就是按层级遍历，计算一最大有多少层。代码如下：
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int depth = 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
int size = q.size();
while(size-- > 0) { // 遍历该层的所有节点，将下一层的节点的left和right都放到队列q中
TreeNode curr = q.poll();
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
depth++; // 该层所有节点遍历完后，该层深度才+1
}
return depth;
}
https://leetcode.com/problems/minimum-depth-of-binary-tree/
这个也没啥好说的，要注意的地方是返回的问题，请查看代码中的注释。
public int minDepth(TreeNode root) {
if (root == null) return 0;
int depth = 1;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
int size = q.size();
while(size-- > 0) { // 遍历该层的所有节点，将下一层的节点的left和right都放到队列q中
TreeNode curr = q.poll();
if (curr.left == null && curr.right == null) {
return depth; // 要注意此时可以直接返回了。因为是按照层级访问，越往后depth越大，所以最先找到的叶子节点必然就是最小的。
}
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
}
depth++;
}
return depth;
}