【算法】利用递归dfs解决二叉树算法题（C++）

1. 前言

有关 递归 的相关解释与解题 请看下文：

以汉诺塔理解递归、并用递归解决算法题

• 对于二叉树，我们曾学过前序遍历，其就是深度优先搜索的一种应用。

  • 在二叉树的前序遍历中，我们首先访问根节点，然后递归对左子树进行前序遍历，最后递归地对右子树进行前序遍历。

• 在深度优先搜索算法中，我们从起始节点开始，递归地探索每个可达节点，直到没有未访问的相邻节点为止。因此，前序遍历也可以看作是对图或树进行深度优先搜索的一种方式。它遵循先访问根节点，然后递归地访问左子节点和右子节点的顺序。

2. 算法题

2331.计算布尔二叉树的值

思路

• 题意分析：对于叶子节点有fals，true；对于非叶子节点有|、&；要求算出最终结果，我们只需要进行深搜，遍历一遍二叉树即可。
• 解法：递归dfs + 前序遍历
  • 函数体：即前序遍历，分别用bool类型记录左右子树值
  • 返回值：当前节点非叶子节点，根据其值判断将左右子树 或还是与
  • 函数出口：即递归出口，当遍历到叶子节点后，通过其值向上返回bool类型。

代码

bool evaluateTree(TreeNode* root) {// 递归// 叶子节点为终止条件if(root->left == nullptr && root->right == nullptr)return root->val == 1 ? true : false;bool left = evaluateTree(root->left);bool right = evaluateTree(root->right);return root->val == 2 ? left | right : left & right;
}

---

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

思路

• 题目要求计算二叉树中所有根节点到叶子节点的路径和，如示例所示，对于[1, 2, 3]的最终结果就是两条路径 12 + 13 = 25
• 解法：递归dfs
  
• 思路如上图所示，以此我们可以完成dfs函数：
  • 函数头：需要接收一个节点以及到该节点时的路径值，且最终返回的也是总的路径值，即int dfs(Node* root, int preSum)
  • 函数体：先统计到当前节点的路径值，再进行左右子树的遍历
  • 终止条件：当遍历到叶子节点，向上返回值

代码

class Solution {
public:// 返回到当前节点计算的所有值int dfs(TreeNode* root, int prevSum) {// 1. 计算prevSum和该节点的数字和int sum = prevSum*10 + root->val;// 2. 终止条件（叶子节点） if(!root->left && !root->right) return sum;// 3.递归左右子树int left = root->left ? dfs(root->left, sum) : 0;int right = root->right ? dfs(root->right, sum) : 0;// 4. 计算出左右子树和并向上返回return left + right;}int sumNumbers(TreeNode* root) {if(!root) return 0;// 递归return dfs(root, 0);}
};

---

LCR047.二叉树剪枝

思路

• 题意分析：题目要求删除二叉树中所有不包含1的子树，则可以利用递归从后向前进行删除。（即通过后序遍历 删除值为0的叶子节点）
• 解法：递归dfs + 后序遍历
  • 函数体：后续遍历，当遇到值为0的叶子节点，将该节点值设为空
  • 函数出口：当遍历到空指针时，向上返回。

代码

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 && !root->right && root->val == 0) {// delete root; // 释放内存：防止内存泄漏root = nullptr; // 置空}return root;}
};

---

98.验证二叉搜索树

思路

• 题意分析：题目要求验证一棵树是否是二叉搜索树。
• 解法：递归dfs + 中序遍历 + 利用二叉搜索树性质
  • 而我们知道，根据二叉搜索树的定义，其中序遍历是有序的，对于BSTree的任意一个节点，其前驱节点一定小于自身
    
  • 据此，我们可以利用中序遍历以及该性质解题：
    • 定义 前驱节点以及一个标记符flag用于标记当前节点是否满足条件。
    • 函数体：中序遍历，对于当前节点判断：如果其前驱节点存在且大于自身，则不是BSTree，将标记符设为false，递归结束。
    • 结束条件：当遍历到空节点或标记符为false时，向上返回

代码

class Solution {
public:TreeNode* prev = nullptr; // 定义全局变量，用于找前驱节点bool flag = true;; // 标记树是否是bstree bool isValidBST(TreeNode* root) {// 递归if(root != nullptr && flag){// 中序遍历isValidBST(root->left);// 如果前一个节点的值大于当前节点的值，则不满足二叉排序树的条件if(prev != nullptr && prev->val >= root->val)flag = false;prev = root; // 更新前驱节点isValidBST(root->right);}return flag;}
};

---

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

思路

• 题意分析：题目要求找到二叉搜索树的倒数第k个最小元素，依照上题的思路，进行中序遍历即可。
• 解法：递归dfs + 中序遍历 + 利用二叉搜索树性质
  • 定义全局变量，省去多次递归创建变量的开销：定义count和ret分别记录k值和结果值
  • dfs函数中进行中序遍历，每次递归–count，直到count==0，此时节点的值就是ret

代码

class Solution {
public:// 全局变量解决递归问题int count, ret;void dfs(TreeNode* root) {// 中序遍历if(!root || count == 0) return;dfs(root->left);--count;if(count == 0)ret = root->val;dfs(root->right);}int kthSmallest(TreeNode* root, int k) {count = k;dfs(root);return ret;}
};

---

257.二叉树的所有路径

思路

• 题意分析：输出所有从根节点到叶子节点的路径。
• 思路：思路很简单，就是直接使用前序遍历即可，对每个节点都加入到字符串中并对字符串后加箭头。
• 解法：递归dfs + 前序遍历
  • 细节问题：
    • 叶子节点不需要加箭头，写代码时另外列出
    • 其余则是对vector和string的使用

代码

class Solution {
public:vector<string> ret; // 最终结果// 如果将path定义为全局变量，则需要手动"恢复现场"// 而作为函数参数，则由函数的性质自动完成了此过程void dfs(TreeNode* root, string path) {// 前序遍历if(root == nullptr) return;// 叶子结点不需要箭头// 将其加入到ret中，并返回if(!root->left && !root->right){path += to_string(root->val);ret.push_back(path);return;}path += to_string(root->val) + "->";dfs(root->left, path);dfs(root->right, path);}vector<string> binaryTreePaths(TreeNode* root) {string path = ""; // 用于记录当前路径dfs(root, path);return ret;}
};