【Leetcode】十六、深度优先搜索 宽度优先搜索 ：二叉树的层序遍历

1、深度优先搜索算法

深度优先搜索，即DFS，从root节点开始，尽可能深的搜索每一个分支。把一个分支的结果搜索完以后，再去看下一个分支。

应用场景：

• 二叉树搜索
• 图搜索

例子：走迷宫，从起点开始，一直走到终点或者撞墙后（这就是所谓的 “深度” 优先），回到起点重新开始，可以找到如下两条路（红色箭头和黄色箭头）

用深度优先来看前面回溯中提到的子集求法：从起点开始，首先是一个空集。往下有1、2、3三条路可以走

先逮着1开始走，1符号要求，放入结果集，接着往下走，[1，2]，也符合要求，放入结果集，接着往下走，[1，2，3]，也符合要求，放入结果集，再往下，就到底了。换另一条路走。

2、宽度优先搜索算法

宽度（广度）优先搜索，即BFS，和DFS不同，BFS是一层一层的处理。BFS一般搭配队列使用。

BFS和DFS的对比：

以从上到下、从左到右遍历以下二叉树为例，采用宽度优先，搭配一个队列，先进先出，计数count = 0。从root开始，root入队，count = 1，出队，同时root的左、右节点入队，并维护count。当count = 0时，说明遍历结束。

即node.val出队，node.left和node.right入队。详细：

• root节点1入队，count = 1
• 根据count，从队列中pop元素，得到root节点，把其值val放入结果集，并把其左右孩子加进来。结果集array = [1]
• 此时，队列中存着2、3这两个节点，count = 2
• 继续根据count = 2来pop两次，并加入元素的左右孩子
• pop出元素2，加入其左右节点4、5，count = 3，结果集array = [1，2]
• pop出元素3，加入其左右节点6、7，count = 4，结果集array = [1，2，3]
• pop出元素4，count = 3，array = [1，2，3，4]
• …
• pop出元素7，count = 0，array = [1，2，3，4，5，6，7]

3、leetcode102：二叉树的层序遍历

和上面分析的BFS遍历二叉树不一样，这题要求输出的结果是分层的，考虑一层一层的处理，并把每层的处理完的结果加入最终的结果集。

外层while执行一次，代表处理了二叉树的一层。内层while执行一次，代表处理这层的每个元素（自身出队、左右节点的值入队）

public class P102 {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (null == root) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (queue.size() > 0) {// 存每层的结果List<Integer> list = new ArrayList<>();// 每处理完一层，队列的长度，即是下一层元素的数量int count = queue.size();// 处理每一层的元素，弹出这一层的每个元素，并把每个元素的左右节点加进去while (count > 0) {TreeNode node = queue.poll();list.add(node.val);count--;// 弹出的元素的左右孩子节点的值入队if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}// 一层处理结束，把结果加到结果集里，注意别直接add上面的list，防止引用传递，用copy值传递result.add(new ArrayList<>(list));}return result;}
}

这题很明显的有”层“的概念，用BFS很合适，但DFS也能解。

从root开始，一条路往下走，和前面一层层的取不一样了，DFS解时，每层递归有个level，level = 0，即root节点所在的那层，放到结果集result的0号位置，往下9，放到result的1号元素里面

public class P102 {public List<List<Integer>> levelOrderByDfs(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (null == root) {return result;}dfs(root, result, 0);return result;}/*** 深度优先** @param node   节点* @param result 最终的结果集* @param level  二叉树中当前的层级*/public static void dfs(TreeNode node, List<List<Integer>> result, int level) {// 终止条件if (node == null) {return;}// 如果当前层级到了2，那结果集里应该初始化出两个元素，每层的结果存一个结果集的元素里if (level > result.size() - 1) {result.add(new ArrayList<>());}// 层级所在结果集的位置上，加入这个元素result.get(level).add(node.val);if (node.left != null) {dfs(node.left, result, level + 1);}if (node.right != null) {dfs(node.right, result, level + 1);}}
}

4、leetcode107：二叉树的层序遍历II

和前面102题不同的是，要求从叶子节点开始一层层的遍历，输出的顺序刚好相反，当然，可以在102的代码的末尾，直接reverse翻转答案，然后return。

说起翻转，也可自己用栈实现，但除了翻转，有更优实现：结果集result用一个链表，依旧从root节点那一层开始，从上往下一层层处理，但每层的结果，加到result的头部，如此，从上到下遍历完每层后，直接不用翻转就是题解。

Java中，List里面底层是链表的，就不能用ArrayList（数组），而是LinkedList：

public class P107 {public List<List<Integer>> levelOrderBottom(TreeNode root) {// 用链表对应的LinkedListList<List<Integer>> result = new LinkedList<>();if (null == root) {return result;}// 队列Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (queue.size() > 0) {int count = queue.size();List<Integer> levelList = new ArrayList<>();for (int i = 0; i < count; i++) {TreeNode node = queue.poll();levelList.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}// 注意这里，每次add的下标是0，即链表队首，这样第二层的结果就会排到第一层result.add(0, levelList);}return result;}
}

以上实现，注意链表的巧妙之处：

这题要不用BFS，而DFS，那最后就得reverse翻转一下结果集了。虽然BFS能解的，DFS也能解，但这种层级的遍历，BFS更好用。

最后，以上用到的TreeNode：

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

5、leetcode938：二叉搜索树的范围和

第一反应是，遍历二叉树，判断每个元素在范围就累加。那应该想到BFS，除了BFS，还有别的实现：不管是前序、中序、后序遍历，一个树，最后肯定会被拆解成一个个只有三个节点的小块，即递归。

解法一：普通递归

从root开始，一分为二的看，最终结果 = 左 + 中 + 右，左边有子树的话，继续左 + 中 + 右，纯递归，递归终止的条件为，节点没有子节点了。代码实现：

public class P938 {public int rangeSumBST(TreeNode root, int low, int high) {if (null == root) {return 0;}// 左边那一块，新的root就是root.leftint leftSum = rangeSumBST(root.left, low, high);// 右边那一块，新的root就是root.rightint rightSum = rangeSumBST(root.right, low, high);int result = leftSum + rightSum;// 中间节点if (low <= root.val && root.val <= high) {result = result + root.val;}return result;}
}

以上面二叉树为例：

- 第一次递归：root=10, left=5，right=15
- 第二次递归：root=上一层的root.left=5，left=3，right=7
- 第三次递归：root=上一层的root.left=3，left=null，right=null
- 第四次递归：root=上一层的root.left=null，终止递归，回退，返回0

解法二：BFS

一层层的来，平铺扫荡，每一个出队的元素，判断是否在范围内，是则累加

这题的BFS，和BFS概念分析时一样，都不用像前两道题一样分层，一层while就行：

public class P938 {public int rangeSumBSTByBFS(TreeNode root, int low, int high) {if (null == root) {return 0;}int result = 0;Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();if (node.val >= low && node.val <= high) {result = result + node.val;}// 左右节点处理if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}return result;}
}