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

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

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

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

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

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

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

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

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

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

我们有如下二叉树

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

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

最后返回计算的和就行了

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);
    }
};

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

1. 返回值：无；

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

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。

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;
 }
};
 
​

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