二叉树深度优先搜索算法与经典例题解析

一、搜索算法

• BFS 和 DFS

  广度优先搜索（BFS）和深度优先搜索（DFS）是两种常用的图和树的遍历算法，遍历是形式，目的是搜索，在某种形式上，遍历算法与搜索算法可以等价。

  BFS 的核心思想是从一个节点开始，逐层遍历所有可达的节点，直到找到目标节点或遍历完所有节点。DFS 的核心思想是从一个节点开始，沿着一条路径尽可能深地搜索，直到无法继续前进时，再回溯到上一个节点，继续搜索其他路径。

• 暴搜

  暴力搜索是一种简单的搜索方式，通过暴力枚举所有的情况来找出结果，通常基于 BFS 和 DFS 实现。暴力搜索通常应用于解决那些没有明显规律或优化方法的问题，尤其是在数据规模较小时，但有时效率会特别低。

二、回溯算法

  回溯算法是一种通过递归搜索所有可能的候选解来找出所有解的算法，它没有那么神秘，本质上其实就是 DFS。回溯算法通常可用于迷宫求解，如下图所示，从起点进入并走出迷宫，按照深搜的思路，沿着一条路径走。如果是死胡同，就回溯走另一条路径，再次按照 DFS，递归搜索和回溯找到迷宫出口。如果在搜索之前，我们知道这个答案不是我们想要的，我们就直接可以舍弃，这个过程就叫剪枝。

三、例题讲解

3.1. 计算布尔二叉树的值

  本题中给出的是完整二叉树，要么没有节点，要么左右孩子节点都有。其中叶子节点储存的是真值，非叶子节点储存的是逻辑与、或。我们以示例 1 为例，0 合取 1，结果为 0；0 析取 1，结果为 1，返回真。

  宏观角度：从上面的示例中我们可以得出，这棵树是从下往上推导的。当我们只看根节点时，我们得知道左子树的值，同时也得知道右子树的值，然后在根节点这一层进行整合。而关于求出左右子树的布尔值，与前面的问题是一样的，只需要传入一个引用，即可返回布尔值，这就是递归方法头与方法体的设计。当我们遍历到叶子节点时，不需要判断它的左右子树是否为空，只需要进行逻辑运算即可，这同时也是递归的出口。

  细节角度：因为计算过程是从下往上，我们可以看作是二叉树的后序遍历。从根节点出发，先去遍历左子树，当遇到叶子节点时，返回该节点的布尔值，然后回溯到它的父亲节点，然后遍历右子树，再回溯父亲节点并遍历自身。