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

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

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