算法设计与实现：基于深度优先搜索的二叉树求值策略（DFS）

Undoom

发布于 2025-07-29 08:32:04

3250

文章被收录于专栏：学习学习

6.计算布尔二叉树的值

题目链接给你一棵 完整二叉树 的根，这棵树有以下特征：

叶子节点 要么值为 0 要么值为 1 ，其中 0 表示 False ，1 表示 True 。
非叶子节点 要么值为 2 要么值为 3 ，其中 2 表示逻辑或 OR ，3 表示逻辑与 AND 。

计算一个节点的值方式如下：

如果节点是个叶子节点，那么节点的值为它本身，即 True 或者 False 。
否则，计算两个孩子的节点值，然后将该节点的运算符对两个孩子值进行运算。

返回根节点 root 的布尔运算值。

完整二叉树 是每个节点有 0 个或者 2 个孩子的二叉树。

叶子节点 是没有孩子的节点。

示例 1：

输入： root = [2,1,3,null,null,0,1] 输出： true 解释： 上图展示了计算过程。 AND 与运算节点的值为 False AND True = False 。 OR 运算节点的值为 True OR False = True 。根节点的值为 True ，所以我们返回 true 。

示例 2：

输入： root = [0] 输出： false 解释： 根节点是叶子节点，且值为 false，所以我们返回 false 。

提示：

树中节点数目在 [1, 1000] 之间。
0 <= Node.val <= 3
每个节点的孩子数为 0 或 2 。
叶子节点的值为 0 或 1 。
非叶子节点的值为 2 或 3 。

深度：dfs

我们得从下往上推才行我们先看左子树是true还是false 再看右子树是true还是false

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution

{

public:

    bool evaluateTree(TreeNode* root)

    {

        //返回条件  当我们当前的节点是叶子节点的话

        if(root->left==nullptr) return root->val==0?false:true;//这里的话我们就不判断右子树了，因为这里是一个完整二叉树，左子树为空，那么右子树也为空。并且我们还需要对val进行判断操作，如果val是0的话，那么就返回false，否则的话就返回true

  

        bool left=evaluateTree(root->left);//先去递归左子树

        bool right=evaluateTree(root->right);//再去递归右子树

  

        //现在我们找到了左右子树的信息了，那么我们就带上我们的根节点进行信息的整合操作

        return root->val==2?left|right:right&left;

    }

};

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

题目链接给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入： root = [1,2,3] 输出： 25 解释： 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此，数字总和 = 12 + 13 = 25

示例 2：

输入： root = [4,9,0,5,1] 输出： 1026 解释： 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此，数字总和 = 495 + 491 + 40 = 1026 提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

相同的子问题当我们到一个节点的时候，我们需要拿到上面的数据，然后将这个数据和当前节点内的数据合并传给左右节点

1.函数头 int dfs(root,presum) 2.函数体将数据获取、合并、传给左右节点 3.递归出口叶子节点

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution

{

public:

    int sumNumbers(TreeNode* root)

    {

        return dfs(root,0);//我们是从0开始的,从根节点开始

    }

  

    int dfs(TreeNode*root,int presum)

    {

        presum=presum*10+root->val;//传给根节点的数据

        //返回条件（出口）到了叶子节点就返回了
        if(root->left==nullptr&&root->right==nullptr)

            return presum;

  

        int ret=0;//返回值

        if(root->left)ret+=dfs(root->left,presum); //满足条件的话直接加等上去左子树的值

        if(root->right)ret+=dfs(root->right,presum);

  

        return ret;

  

    }

};

8.二叉树剪枝

题目链接给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例 1：

输入： root = [1,null,0,0,1] 输出：[1,null,0,null,1] 解释： 只有红色节点满足条件“所有不包含 1 的子树”。右图为返回的答案。

示例 2：

输入： root = [1,0,1,0,0,0,1] 输出：[1,null,1,null,1]

示例 3：

输入： root = [1,1,0,1,1,0,1,0] 输出：[1,1,0,1,1,null,1]

提示：

树中节点的数目在范围 [1, 200] 内
Node.val 为 0 或 1

将节点里面的值都是0的数删除了只要子树里面都是0，那么我们就将这个树抹掉

这个题肯定是一个后续遍历的，因为我们需要知道左子树和右子树的信息，看看是否为0

1.函数头 Node* dfs(root)

2.函数体 1.处理左子树 2.处理右子树 3.判断 3.递归出口当root== null

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution

{

public:

    TreeNode* pruneTree(TreeNode* root)

    {

        //递归出口

        if(root==nullptr) return nullptr;//如果当前根节点是空的话，那么我们就返回

  

        //将当前根节点的左子树和右子树的0节点删除

        root->left=pruneTree(root->left);

        root->right=pruneTree(root->right);

  

        if(root->left==nullptr&&root->right==nullptr&&root->val==0)//如果左右子树为空，并且根节点值为0，那么我们就删除

        {

            //将当前根节点置为空

            //delete root;//防止内存泄漏

            root=nullptr;

        }

        return root;//返回根节点

  

    }

};

如果我们节点是new出来的话我们就可以delete了，这样可以防止内存泄漏

9.验证二叉搜索树

题目链接给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入： root = [2,1,3] 输出： true

示例 2：

输入： root = [5,1,4,null,null,3,6] 输出： false 解释： 根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

左子树小于根节点，右子树大于根节点

二叉搜素树的中序遍历的结果，是一个有序的序列这个题的话我们可以借助全局变量+中序遍历解决这个题

策略一：左子树是二叉搜索树当前节点符合二叉搜索树的定义右子树也是二叉搜索树

策略二：当我们发现某个节点不符合条件的话，不是二叉搜索树的话，那么我们就没必要往后面进行搜索了，直接从这个位置向上返回false就行了

减枝的操作加快了我们的搜索过程

策略一的代码，代码很暴力，将整棵树都进行了遍历的操作

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution

{

    long prev=LONG_MIN;//全局变量遍历树

public:

    bool isValidBST(TreeNode* root)

    {

        if(root==nullptr) return true;//如果根节点是空的话，那么这也是个二叉搜索树了

        auto left=isValidBST(root->left);//获取左子树的返回节点

        bool cur=false;//来标记我们当前数是不是二叉搜索树

        if(root->val>prev)//如果根节点的值大于前驱的值的话，那么就满足条件

        {

            cur=true;

        }

        prev=root->val;

        //去右子树看看是不是二叉搜索树

        auto right=isValidBST(root->right);

  

        return left&&right&&cur;//判断这个树是否是一个合格的二叉搜索树，利用这三个变量

    }

};

策略二：剪枝我们在遍历左子树后面加上if(left==false) return false;就行了，如果左子树返回的是false的话，那么我们就没有必要往后进行遍历的操作了

我们在判断完当期节点是否符合要求后，如果cur被改变成true的话，就说明这个节点是不符合要求的，所以我们直接返回false就行了

这个代码一共有两处剪枝的操作，都可以提高效率，不用一个个节点的遍历

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution

{

    long prev=LONG_MIN;//全局变量遍历树

public:

    bool isValidBST(TreeNode* root)

    {

        if(root==nullptr) return true;//如果根节点是空的话，那么这也是个二叉搜索树了

        auto left=isValidBST(root->left);//获取左子树的返回节点

        //剪枝操作

        if(left==false) return false;

        bool cur=false;//来标记我们当前数是不是二叉搜索树

        //判断当前节点是否符合要求

        if(root->val>prev)//如果根节点的值大于前驱的值的话，那么就满足条件

        {

            cur=true;

        }

        //剪枝操作

        if(cur==false )return false;//如果我们当前节点为false的话，我们直接返回false

        prev=root->val;

        //去右子树看看是不是二叉搜索树

        auto right=isValidBST(root->right);

  

        return left&&right&&cur;//判断这个树是否是一个合格的二叉搜索树，利用这三个变量

    }

};

这里的话我们的代码是中序遍历左子树->中子树->右子树依次进行判断操作

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

题目链接给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

输入： root = [3,1,4,null,2], k = 1 输出： 1

示例 2：

输入： root = [5,3,6,2,4,null,null,1], k = 3 输出： 3

提示：

树中的节点数为 n 。
1 <= k <= n <= 104
0 <= Node.val <= 104

进阶： 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

两个全局变量+一个中序遍历就可以解决问题了

二叉搜索树的中序遍历是一个有序数组并且我们这里可以使用剪枝的操作，当我们找到结果后，我们可以就可以停止了后面的遍历了，直接终止递归操作，直接向上返回就行了

两个全局变量，count=k，遍历一次就减去1，直到count减到0，那么此时的数就是第k小的数了，那么我们再用另一个变量ret进行标记操作，返回就行了

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution

{

    int count;//用来计数的

    int ret;//返回最终的结果

public:

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

    }

};

11.二叉树的所有路径

题目链接给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。 示例 1：

输入： root = [1,2,3,null,5] 输出：[“1->2->5”,“1->3”]

示例 2：

输入： root = [1] 输出：[“1”]

提示：

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

我们这里使用全局变量path进行恢复现场的话很难操作我们将这个path搞成一个参数放到函数中，函数帮助我们恢复现场

函数头：void dfs(root,path)

函数体： if(root== 叶子节点) 我们将这个节点的path丢到ret中

如果不是叶子节点的话，我们添加完当前的数添加箭头

递归出口：当前节点为空的话，我们直接返回

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}

 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

 * };

 */

class Solution

{

public:

    vector<string> ret;//记录结果

    vector<string> binaryTreePaths(TreeNode* root)

    {

        string path;

        dfs(root,path);

        return ret;

    }

    void dfs(TreeNode*root,string path)//这里我们不需要在path前面加引用，加上了就说明这个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);

    }

};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-07-28，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树