算法学习（十四）—— 二叉树的深度搜索（DFS）

目录

关于dfs

部分OJ题详解

2331. 计算布尔二叉树的值

129. 求根节点到叶节点数字之和

814. 二叉树剪枝

98. 验证二叉搜索树

230. 二叉搜索树中第K小的元素

257. 二叉树的所有路径

关于dfs

算法学习（十二）—— 递归，搜索，回溯前置_数组递归查找-CSDN博客

部分OJ题详解

2331. 计算布尔二叉树的值

2331. 计算布尔二叉树的值 - 力扣（LeetCode）

题目有点长，得结合示例来理解。下面来分析下这道题：

• 看到二叉树遍历，最先想到的就是递归，这里我们用DFS来尝试解决
• 在这道题的树中，只要节点有孩子，那必定有两个子节点，没有只有一个子节点的情况；非叶结点里面存的是“逻辑与”或“逻辑或”，叶子节点存的就是1或0，也就是“true”或“false”
• 然后就是发现子问题的过程了，以根节点为例，假如我要知道根节点最后的值是什么，那我就得直到左子树和右子树的值是多少，然后以左子树或右子树的根节点为例，再往下进行同样的分析，就发现了我们的相同子问题，所以我们的函数头就是：bool dfs(root); 也就是你给我一个根节点，我告诉你最后的结果是true还是false
• 然后就是函数体的设计，bool left = dfs(root->left);  bool right = dfs(root->right);  也就是要告诉我们左右子树的值，然后就是根据目前的根节点是“逻辑与”还是“逻辑或”，算出结果
• 最后就是递归出口，就是当我遇到叶子节点的时候，直接返回true或false即可 

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

129. 求根节点到叶节点数字之和

 129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

下面来分析下这道题：

• 我们仍然还是尝试用递归的dfs来尝试解决下，还是那三个步骤：找相同子问题，搞清楚每个子问题要做什么，递归出口
• 首先是相同子问题，上面示例的树太小了，我们换个大的树，如下图：
• 
• 所以函数头设计为：int dfs(root, presum); 也就是传一个根节点，以及这个根节点前面路径的值presum传给后面，然后给我返回这个根节点最后计算的值
• 函数体的步骤就是：①先算出该根节点加上前面路径的计算结果值    ②把这个值传给左子树    ③把这个值传给右子树    ④左右子树返回计算结果 
• 递归出口就是当遇到叶子节点时，把上面的第一步计算完之后，再正式返回，不再将这个值传给左右子树

class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root, 0);}int dfs(TreeNode* root, int prevsum){prevsum = prevsum * 10 + root->val; //①if(root->left == nullptr && root->right == nullptr) return prevsum; //递归出口int ret = 0;if(root->left != nullptr) ret += dfs(root->left, prevsum); //②if(root->right != nullptr) ret += dfs(root->right, prevsum); //③return ret; //④}
};

814. 二叉树剪枝

814. 二叉树剪枝 - 力扣（LeetCode）

题目的意思很明确，就是如果一个节点的子树中没有值为1的节点的话，就把这个子树干掉，下面我们来分析下这道题：

• 这个题目和我们之前的题目有点不一样，前面的题目就是让我们根据信息求值，没有改变二叉树，而这个题目是要求我们实实在在的对二叉树做了修改了。还是用递归的dfs来尝试解决这道题还是三个问题
• 先来看下如何找到相同的子问题：当我遍历到一个节点时，我们要做的就是“这个节点是否应该被剪掉”，依据就是“这个节点的子树是否含有值为1的节点”，所以这道题一定是后序遍历，因为只有后序遍历才有机会回到根节点的时候带着左右子树的信息
• 当遍历到叶节点时，已经没有左右子树了，并且如果我自己也是0，就把我自己干掉，回到父节点后，还要修改下父节点的指针，这一步可以通过返回值解决，就是把父节点的指针修改成这个返回值即可，所以函数头需要有一个返回值Node*
• 如果已经是叶节点，但我自己是1，那么就不需要把我干掉，就把我自己的指针向上返回，就一直通过上面的步骤，就可以干掉所有符合要求的子树，所以函数头的设计就是：Node* dfs(root);
• 然后就是函数体的设置，基本步骤和上面的一样：①处理左子树    ②处理右子树    ③判断是否为叶结点并且判断是否为1，进行剪枝操作并返回
• 最后是递归出口，就是当root == null 的时候，直接返回

class Solution {
public:TreeNode* pruneTree(TreeNode* root) {return dfs(root);}TreeNode* dfs(TreeNode* root){if(root == nullptr) return root;root->left = dfs(root->left);root->right = dfs(root->right);if(root->left == nullptr && root->right == nullptr && root->val == 0)root = nullptr;return root;}
};

98. 验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

 

这道题我们主要是理解三个点：①理解全局变量的优势    ②回溯    ③剪枝；后面会给出两种思路和代码，一个是有剪枝的，一种没有剪枝，下面来分析下这道题：

•  二叉搜索树的中序遍历结果，是一个有序的序列，所以，我们可以验证这棵树的中序遍历结果是否有序即可，这个可以用一个全局变量来搞
• 先搞一个全局变量 “prev = 负无穷大”，然后每次中序遍历时，都更新一下 prev的值，以上面的示例2为例，根据中序遍历，假设遍历到4的位置，prev此时的值为3，然后将此时节点的值和prev作比较验证有序即可，最后就是遍历到5，prev再次更新为4，再次比较即可，所以只要和prev作比较然后返回true或false即可

策略一，也就是上面的方法：

• 验证左子树是二叉搜索树
• 当前遍历的节点符合二叉搜索树的定义
• 验证右子树是二叉搜索树 

策略二，剪枝：

•  还是以示例二为例，假设递归已经完成了验证左子树是二叉搜索树，此时prev是5
• 当中序遍历到3时，3小于5，所以已经不符合二叉搜索树的定义了，此时我们直接一路返回false到根节点，不再去比较节点6了，这就是剪枝，意义就是加快搜索过程

无剪枝代码：

class Solution 
{
public:long prev = LONG_MIN;bool isValidBST(TreeNode* root) {return dfs(root);  }bool dfs(TreeNode* root){if(root == nullptr) return true;bool left = dfs(root->left);bool cur = false; //cur表示当前节点是否满足二叉搜索树条件if(root->val > prev) cur = true;prev = root->val;bool right = dfs(root->right);return left && right && cur;}
};

 剪枝：

class Solution 
{
public:long prev = LONG_MIN;bool isValidBST(TreeNode* root) {return dfs(root);  }bool dfs(TreeNode* root){if(root == nullptr) return true;bool left = dfs(root->left);if(left == false) return false; //剪枝：就是当左子树已经不符合搜索二叉树了，直接返回bool cur = false; //cur代表当前节点是否满足二叉搜索树条件if(root->val > prev) cur = true;if(cur == false) return false; //如果我当前位置节点已经不符合二叉搜索树要求了，直接返回，不再去遍历右子树了，这就是剪枝prev = root->val;bool right = dfs(root->right);return left && right && cur;}
};

230. 二叉搜索树中第K小的元素

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）

这道题题意还是很简单的，也是给我们一个二叉搜索树，然后让我们返回这个树的节点中值第K小的值，下面来分析下这道题：

• 有了上一道题的经验之后，这道题其实超级简单，因为我们已经知道了“二叉搜索树的中序遍历结果是有序的”，所以我们就可以用“ 两个全局遍历 + 中序遍历 ”就可以解决这道题
• 以上面的示例二为例，搞两个全局遍历，count = k = 3，ret = 0，ret的作用就是当count一直减减到0时，用ret标记一下当前节点的值然后返回
• 这里可以用剪枝，就是当count为0时，直接返回后面的步骤都不再执行，这就是剪枝，这一步加个判断即可

 

class Solution {
public:int count;int ret;int kthSmallest(TreeNode* root, int k) {count = k;dfs(root);return ret;}void dfs(TreeNode* root){if(root == nullptr || count <= 0) return;dfs(root->left);count--;if(count == 0) ret = root->val;dfs(root->right);}
};

257. 二叉树的所有路径

257. 二叉树的所有路径 - 力扣（LeetCode）

前面两道题我们提到了三个词：①全局变量    ②回溯    ③剪枝，其中回溯有个性质叫做“恢复现场”

关于恢复现场：

网上很多人在自学算法的时候，都是看到了代码中有“恢复现场”的操作，才知道这道题用了“回溯”，所以很多人以为的就是“恢复现场 --> 回溯”

而今天，我们就要把这个因果关系给反过来：

• 如果有递归，那么肯定有回溯：递归 --> 回溯
• 如果有回溯，那么肯定有“恢复现场”：回溯 --> 恢复现场
• 所以，如果有递归，那么就有恢复现场：递归 --> 恢复现场

在后面的难度较高的递归回溯题目的时候，有了“回溯 --> 恢复现场”的思路之后，写代码的过程才会有思路，并且，一旦我们在题目中用到了全局变量，那么恢复现场的操作就会显得很重要

这个题目很简单，就是让我们把每一个路径保存在一个字符串数组里面，具体步骤通过示例一和示例二很好理解，下面来分析下这道题：

• 思路很简单，就是在搜索的过程中，记录每一个节点即可，当遇到叶子节点的时候停止搜索
• 我们可以搞两个全局变量，①一个字符串数组 string[] ret：就是在我遍历时发现叶子节点时，就把结果扔 ret 里去；    ②一个字符串变量 string path：作用就是在深度遍历的时候，记录一下路径，以示例一为例，遍历到1时，path的值为“1->”；当遍历到2时，path的值为“1->2>”；当遍历到5时，由于5是叶节点，所以只添加数字，所以最后path的值为“1->2->5”
• 但是前面说过，有递归就有回溯，当遍历完5，回溯到1时，接下来就是要往右边回溯，但是此时path的值不是从1开始的“1->”，而是还是之前的“1->2->5”，所以我们需要“恢复现场”，就是我们在向上返回的时候，需要不断pop掉path的结尾，但是又因为是全局path，需要很多很多次的添加和删除，不太好控制，所以这道题我们不用全局的path，后面再用
• 那么用什么代替全局path呢？我们可以在函数头设置一下：void dfs(root, path);  如果我们把path当作参数传递，那么就是每次调用path的时候，相当于重新创建了一个path变量，也就是每次深度搜索时，都用的是自己单独地path变量，代替了“恢复现场”的操作和功能
• 然后激素关心一下每一个子问题在干什么，也激素函数体的设置：如果root是叶子节点，只在path后面添加上数字即可；如果root不是叶子节点，dfs(root->left, path); dfs(root->right, path)
• 最后就是递归出口，就是注意一下剪枝：当左子树为空时，就不需要再 dfs(root->left)了，直接去搞右子树即可：if(root == nullptr) return;  

class Solution {
public:vector<string> ret;vector<string> binaryTreePaths(TreeNode* root) {string path;if(root == nullptr) return ret;dfs(root, path);return ret;}void dfs(TreeNode* root, string path){path += to_string(root->val);if(root->left == nullptr && root->right == nullptr) //如果是叶子节点，直接返回，不再搜索{ret.push_back(path);return;}path += "->";if(root->left) dfs(root->left, path);if(root->right) dfs(root->right, path);}
};