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

【二叉搜素树】——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:// 主函数,调用辅助的深度优先搜索函数,初始累加和为0int 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,且当前节点符合条件时,返回truereturn 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);// 访问当前节点,更新 countcount--;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.lryc.cn/news/484825.html

相关文章:

  • 【计算机视觉】FusionGAN
  • 问:SQL优化,七条实践总结?
  • unity单例模式的不同声明(待完善
  • 大模型在蓝鲸运维体系应用——蓝鲸运维开发智能助手
  • vue2,vue3响应式的理解
  • 群控系统服务端开发模式-应用开发-前端退出功能
  • Web入门
  • 基于SpringBoot网上超市的设计与实现录像
  • python爬虫(二)爬取国家博物馆的信息
  • 【mysql的当前读和快照读】
  • [CKS] Audit Log Policy
  • 【Linux】-学习笔记03
  • Leetcode热题100-32 最长有效括号
  • 【大数据学习 | HBASE】hbase的读数据流程与hbase读取数据
  • A027-基于Spring Boot的农事管理系统
  • Redisson的可重入锁
  • SQL Server Service Broker完整示例
  • CentOS7 升级OpenSSH9.0全过程和坑
  • RSTP的配置
  • 力扣257:二叉树的所有路径
  • Tcl 和 Python 在二次开发研究
  • 【NLP优化】Ubuntu 20.04 下 源码安装 CasADi + Ipopt / acados
  • [241110] 微软发布多智能体系统Magentic-One | 社区讨论:Ubuntu 26.04 LTS 发布前移除 Qt 5
  • AI风向标|算力与通信的完美融合,SRM6690解锁端侧AI的智能密码
  • MySQL查询执行(六):join查询
  • python习题练习
  • MySQL高级(二):一条更新语句是如何执行的
  • 在 Ubuntu 18.04 中搭建和测试 DNS 服务器
  • 算法学习第一弹——C++基础
  • javaWeb小白项目--学生宿舍管理系统