当前位置: 首页 > article >正文

【二叉搜素树】——LeetCode二叉树问题集锦:6个实用题目和解题思路

文章目录

  • 计算布尔二叉树的值
  • 求根节点到叶节点的数字之和
  • 二叉树剪枝
  • 验证二叉搜索树
  • 二叉搜索树中第K小的元素
  • 二叉树的所有路径

计算布尔二叉树的值

解题思路:

  • 这是一个二叉树的布尔评估问题。树的每个节点包含一个值,其中叶子节点值为 0 或 1,非叶子节点值为 2(表示 OR 操作)或 3(表示 AND 操作)。
    可以使用递归来评估布尔树:
    如果当前节点是叶子节点,直接返回其布尔值(0 为 False,1 为 True)。
    否则,递归评估左右子树。
    如果当前节点值为 2,返回左右子树的“或”运算结果;如果为 3,返回“与”运算结果。

在这里插入图片描述

class Solution 
{
public:
    bool evaluateTree(TreeNode* root) 
    {
        // 如果是叶节点,返回节点值的布尔结果
        if(root->left == nullptr) return root->val == 0 ? false : true;

        // 递归计算左子树的布尔值
        auto left = evaluateTree(root->left);
        // 递归计算右子树的布尔值
        auto right = evaluateTree(root->right);

        // 根据节点值来决定使用哪种布尔运算
        // 2 表示 OR 运算,3 表示 AND 运算
        return root->val == 2 ? left | right : left & right;    
    }
};

求根节点到叶节点的数字之和

解题思路:

  • 要计算从根节点到叶节点路径所表示的所有数字的总和。
    递归遍历每条路径,沿途维护一个当前的数字值,将每个节点的值添加到数字的末尾。
    如果到达叶子节点,将当前生成的数字添加到总和中。
    返回所有根到叶路径数字的总和。

在这里插入图片描述

class Solution 
{
public:
    // 主函数,调用辅助的深度优先搜索函数,初始累加和为0
    int sumNumbers(TreeNode* root) 
    {
        return dfs(root, 0);
    }

    // 深度优先搜索函数,用于计算从根到叶节点的路径和
    int dfs(TreeNode* root, int presum)
    {
        // 将当前节点的值加入路径值,乘以10以表示其位数
        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;
    }
};

二叉树剪枝

解题思路:

  • 需要剪除二叉树中所有的子树,如果整个子树中没有 1,就删除该子树。
    可以使用后序遍历递归判断每个节点的左右子树:
    先递归处理左子树和右子树。
    如果左子树没有 1,则将左子树置为 None;如果右子树没有 1,则将右子树置为 None。
    最后,判断当前节点是否为 1 或其子树是否包含 1,如果都没有,返回 None,否则返回当前节点。

在这里插入图片描述

class Solution 
{
public:
    // 主函数,调用递归函数修剪二叉树
    TreeNode* pruneTree(TreeNode* root) 
    {
        // 如果节点为空,直接返回空
        if (root == nullptr) return nullptr;

        // 递归处理左子树和右子树
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);

        // 如果当前节点的值为0,且左右子树均为空,删除当前节点(设为nullptr)
        if (root->left == nullptr && root->right == nullptr && root->val == 0)
        {
            root = nullptr;
        }
        
        // 返回处理后的节点
        return root;
    }
};

验证二叉搜索树

解题思路:

  • 验证二叉树是否为二叉搜索树(BST),即所有左子树节点值均小于当前节点,所有右子树节点值均大于当前节点。
    可以通过递归设定上下边界来验证每个节点:
    对于根节点,其值在 (−∞, +∞) 范围内。
    对于左子节点,设定其值范围为 (min, 当前节点值)。
    对于右子节点,设定其值范围为 (当前节点值, max)。
    如果所有节点都符合条件,则该树是 BST。

在这里插入图片描述

class Solution 
{
    long prev = LONG_MIN; // 用于记录前一个节点的值,初始为最小值
public:
    // 验证二叉搜索树的主函数
    bool isValidBST(TreeNode* root) 
    {
        // 如果节点为空,说明是合法的子树
        if (root == nullptr) return true;

        // 检查左子树是否为有效的二叉搜索树
        bool left = isValidBST(root->left);

        // 当前节点的有效性检查
        bool ret = false;
        if (root->val > prev) ret = true; // 当前节点值必须大于前一个节点值
        prev = root->val; // 更新前一个节点的值

        // 检查右子树是否为有效的二叉搜索树
        bool right = isValidBST(root->right);

        // 只有左子树、右子树都是有效BST,且当前节点符合条件时,返回true
        return left && right && ret; 
    }
};

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

解题思路:

  • 由于 BST 的中序遍历会按从小到大的顺序输出节点值,因此可以通过中序遍历找到第 k 小的元素。
    进行中序遍历并计数,当计数达到 k 时,当前节点即为第 k 小的节点。
    优化:如果只找到第 k 小的节点后停止遍历,可以减少不必要的遍历。

在这里插入图片描述

class Solution 
{
    int count; // 记录剩余的步数,找到第 k 小的元素
    int ret;   // 用于存储第 k 小的元素值
public:
    // 主函数,初始化 count 并调用深度优先搜索
    int kthSmallest(TreeNode* root, int k) 
    {
        count = k;
        dfs(root);
        return ret;
    }

    // 中序遍历二叉搜索树的递归函数
    void dfs(TreeNode* root)
    {
        // 如果节点为空,直接返回
        if (root == nullptr) return;

        // 递归遍历左子树
        dfs(root->left);

        // 访问当前节点,更新 count
        count--;
        if (count == 0) ret = root->val; // 当 count 减到 0 时,找到第 k 小的元素

        // 递归遍历右子树
        dfs(root->right);
    }
};

二叉树的所有路径

解题思路:

  • 需要找到二叉树中所有从根节点到叶节点的路径。
    通过 DFS(深度优先搜索)来遍历每一条路径,沿途构建路径字符串:
    如果当前节点是叶节点,将当前路径字符串加入结果列表。
    如果不是叶节点,继续递归其左右子树,构建路径字符串(添加 -> 以表示路径)。
    最终返回所有路径的字符串列表。

在这里插入图片描述

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

http://www.kler.cn/a/393233.html

相关文章:

  • 【开源免费】基于SpringBoot+Vue.JS安康旅游网站(JAVA毕业设计)
  • 4.3 数据库HAVING语句
  • MyBatis如何处理延迟加载?
  • 数据结构之栈,队列,树
  • 《Cocos Creator游戏实战》非固定摇杆实现原理
  • Java技术专家视角解读:SQL优化与批处理在大数据处理中的应用及原理
  • 除了 Postman,还有什么好用的 API 测试工具吗
  • uni-app中使用 unicloud 云开发平台③
  • C++生成随机数
  • 信用租赁系统的灵活配置与智能化管理助力租赁市场发展
  • 29系统备份与恢复
  • 深入理解 Vue v-model 原理与应用
  • 量化交易系统开发-实时行情自动化交易-4.1.1.A股趋势跟踪交易策略实现
  • 批量缓存模版
  • 基于yolov5的番茄成熟度检测系统,支持图像、视频和摄像实时检测【pytorch框架、python源码】
  • 【前端篇】Node.js 版本管理新选择:Volta,让版本切换更简单
  • OpenGL 进阶系列07 - 阴影贴图(shadowmap )
  • 【深度学习】使用硬件加速模型训练速度
  • Scala可变List
  • MySQL —— MySQL基础概念与常用功能介绍
  • VScode下脚本被禁止运行的原因及解决方案
  • python 怎么在模块和文件夹名称不一致的情况下,安装自己的模块
  • 物联网设备研究——分配推理负载的联合学习方法
  • Android Studio 中三方库依赖无法找到的解决方案
  • 算法和数据结构 目录
  • 使用 VS Code 远程连接时解决 OpenSSL 版本不匹配及权限问题