[算法] 第二集 二叉树中的深度搜索

深度优先遍历（DFS，全称为 Depth First Traversal），是我们树或者图这样的数据结构中常⽤的

⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分支，直到⼀条路径上的所有节点都被遍历

完毕，然后再回溯到上⼀层，继续找⼀条路遍历。

在⼆叉树中，常见的深度优先遍历为：前序遍历、中序遍历以及后序遍历。

因为树的定义本⾝就是递归定义，因此采⽤递归的方法去实现树的三种遍历不仅容易理解⽽且代码很简洁。并且前中后序三种遍历的唯⼀区别就是访问根节点的时机不同，在做题的时候，选择⼀个适当的遍历顺序，对于算法的理解是非常有帮助的。

一、计算布尔二叉树的值

1.题目描述

2.算法思路

书面解释就是：

1. 对于规模为 n 的问题，需要求得当前节点值。

2. 节点值不为 0 或 1 时，规模为 n 的问题可以被拆分为规模为 n-1 的子问题：

a. 所有子节点的值；

b. 通过子节点的值运算出当前节点值。

3. 当问题的规模变为 n=1 时，即叶⼦节点的值为 0 或 1，我们可以直接获取当前节点值为 0 或 1。

画图来理解一下：

我们如果想知道根节点true or false，我们需要知道其子节点，true or false，进而层层递归

3.代码实现

class Solution
{
public:bool evaluateTree(TreeNode* root) {if(root->left == nullptr) {return root->val == 0 ? false : true;}bool left = evaluateTree(root->left);bool right = evaluateTree(root->right);return root->val == 2 ? left | right : left & right;}
};

二、求根节点到叶节点数字之和

1.题目描述

2.算法思路

通过前序遍历，往左右子树传递信息，并且在回溯时得到左右子树的返回值。让递归函数完成两件事：

1. 将父节点的数字与当前节点的信息整合到⼀起，计算出当前节点的数字，然后传递到下⼀层进行递归；

2. 当遇到叶子节点的时候，就不再向下传递信息，将整合的结果向上⼀直回溯到根节点。

在递归结束时，根节点需要返回的值也就被更新为了整棵树的数字和。

递归函数设计：int dfs(TreeNode* root, int num)

1. 返回值：当前子树计算的结果（数字和）；

2. 参数 num：递归过程中往下传递的信息（父节点的数字）；

3. 函数作用：整合父节点的信息与当前节点的信息计算当前节点数字，并向下传递，再回溯时返回当前子树（当前节点作为子树根节点）数字和。

我们画图来理解一下,举个例子:

我们有如下二叉树

首先,我们 合父节点的信息与当前节点的信息计算当前节点数字，并向下传递:

溯时返回当前子树（当前节点作为子树根节点）数字和:

最后返回计算的和就行了

递归函数流程：

1. 当遇到空节点的时候，说明这条路从根节点开始没有分⽀，返回 0；

2. 结合⽗节点传下的信息以及当前节点的 val，计算出当前节点数字 sum；

3. 如果当前结点是叶子节点，直接返回整合后的结果 sum；

4. 如果当前结点不是叶父节点，将 sum 传到左右子树中去，得到左右子树中节点路径的数字和，然 后相加后返回结果。

3.代码实现

class Solution {
public:int dfs(TreeNode* root, int prevSum) {if (root == nullptr) {return 0;}int sum = prevSum * 10 + root->val;if (root->left == nullptr && root->right == nullptr) {return sum;} else {return dfs(root->left, sum) + dfs(root->right, sum);}}int sumNumbers(TreeNode* root) {return dfs(root, 0);}
};

三、二叉树剪枝

1.题目描述

2.算法思路

如果我们选择从上往下删除，我们需要收集左右⼦树的信息，这可能导致代码编写相对困难。然而， 通过观察我们可以发现，如果我们先删除最底部的叶子节点，然后再处理删除后的节点，最终的结果并不会受到影响。 因此，我们可以采⽤后序遍历的方式来解决这个问题。在后序遍历中，我们先处理左子树，然后处理 右子树，最后再处理当前节点。在处理当前节点时，我们可以判断其是否为叶子节点且其值是否为 0，

如果满足条件，我们可以删除当前节点。

• 需要注意的是，在删除叶子节点时，其父节点很可能会成为新的叶子节点。因此，在处理完子节点后，我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因（后序遍历⾸先遍历到的一定是叶子节点）。

• 通过使用后序遍历，我们可以逐步删除叶子节点，并且保证删除后的节点仍然满足删除操作的要

求。这样，我们可以较为方便地实现删除操作，而不会影响最终的结果。

• 若在处 理结束后所有叶子节点的值均为 1，则所有子树均包含 1，此时可以返回。

算法流程：

递归函数设计：void dfs(TreeNode*& root)

1. 返回值：无；

2. 参数 ：当前需要处理的节点；

3. 函数作用：判断当前节点是否需要删除，若需要删除，则删除当前节点。

后序遍历的主要流程：

1. 递归出口：当传入节点为空时，不做任何处理；

2. 递归处理左子树；

3. 递归处理右子树；

4. 处理当前节点：判断该节点是否为叶⼦节点（即左右⼦节点均被删除，当前节点成为叶子节点），

并且节点的值为 0：

a. 如果是，就删除掉；

b. 如果不是，就不做任何处理。

3.代码实现:

class Solution
{
public:TreeNode* pruneTree(TreeNode* root) {if(root == nullptr) return nullptr;root->left = pruneTree(root->left);root->right = pruneTree(root->right);if(root->left == nullptr && root->right == nullptr && root->val == 0){delete root; // 防⽌内泄漏root = nullptr;}return root;}
};

四、验证二叉搜索树

1.题目描述

2.算法思路

 如果一棵树是二叉搜索树，那么它的中序遍历的结果一定是⼀个严格递增的序列。 因此，我们可以初始化⼀个无穷小的全区变量，用来记录中序遍历过程中的前驱结点。那么就可以在中序遍历的过程中，先判断是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传入下一层的递归中。

算法流程：

1.  初始化⼀个全局的变量 prev，⽤来记录中序遍历过程中的前驱结点的 val；
2.  中序遍历的递归函数中：
   a. 设置递归出⼝：root == nullptr 的时候，返回 true；
   b. 先递归判断左⼦树是否是⼆叉搜索树，⽤ retleft 标记；
   c. 然后判断当前结点是否满⾜⼆叉搜索树的性质，用 retcur 标记：
   ▪ 如果当前结点的 val ⼤于 prev，说明满足条件，retcur 改为 true；
   ▪ 如果当前结点的 val ⼩于等于 prev，说明不满⾜条件，retcur 改为 false；
   d. 最后递归判断右⼦树是否是⼆叉搜索树，⽤ retright 标记；
3. 只有当 retleft、 retcur 和 retright 都是 true 的时候，才返回 true。

3.代码实现

class Solution 
{
public:long prev = LONG_MIN;bool isValidBST(TreeNode* root) {if(root == nullptr) return true;bool left = isValidBST(root->left);// 剪枝if(left == false) return false;bool cur = false;if(root->val > prev)cur = true;// 剪枝if(cur == false) return false;prev = root->val;bool right = isValidBST(root->right);return left && right && cur;}
};​

---

感谢大家的观看，如有错误欢迎指正！