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

[数据结构+算法] 给一棵树和一个sum,判断是否存在从root到叶子结点的path之和等于sum?

[数据结构+算法] 给一棵树和一个sum,判断是否存在从root到叶子结点的path之和等于sum?

可以使用两种方法求解

  • 递归 CheckTreeSumRecursive

问题转换为递归判断左右子树是否满足路径和等于sum减去当前节点的值。

  • 迭代 CheckTreeSumNonRecursive

使用两个栈数据结构,一个存储节点,另一个存储对应的节点到root节点到sum,迭代遍历到叶子节点时进行判断。

详细代码如下:

#include <iostream>
#include <stack>using namespace std;struct TreeNode {TreeNode(int val_) : val(val_), left(nullptr), right(nullptr) {}int val;TreeNode *left;TreeNode *right;
};bool CheckTreeSumRecursive(TreeNode *head, int targetSum) {if (head == nullptr) {return false;}if (head->left == nullptr && head->right == nullptr && head->val == targetSum) {return true;}return CheckTreeSumRecursive(head->left, targetSum - head->val) || CheckTreeSumRecursive(head->right, targetSum - head->val);
}bool CheckTreeSumNonRecursive(TreeNode *head, int targetSum) {if (head == nullptr) {return false;}stack<TreeNode*> nodes;nodes.push(head);stack<int> sums;sums.push(head->val);while (!nodes.empty()) {TreeNode *node = nodes.top();nodes.pop();int sum = sums.top();sums.pop();if (node->left == nullptr && node->right == nullptr && sum == targetSum) {return true;}if (node->left != nullptr) {nodes.push(node->left);sums.push(sum + node->val);}if (node->right != nullptr) {nodes.push(node->right);sums.push(sum + node->val);}}return false;
}// 打印结果的辅助函数
void printResult(bool result) {cout << (result ? "true" : "false") << endl;
}int main() {// 创建示例二叉树TreeNode* root = new TreeNode(5);root->left = new TreeNode(4);root->right = new TreeNode(8);root->left->left = new TreeNode(11);root->left->left->left = new TreeNode(7);root->left->left->right = new TreeNode(2);root->right->left = new TreeNode(13);root->right->right = new TreeNode(4);root->right->right->right = new TreeNode(1);cout << "Test Recursive Solution...\n";cout << "Example 1: ";printResult(CheckTreeSumRecursive(root, 22)); // 输出 truecout << "Example 2: ";printResult(CheckTreeSumRecursive(root, 5)); // 输出 falsecout << "Example 3: ";printResult(CheckTreeSumRecursive(nullptr, 0)); // 输出 falsecout << "Test Recursive Solution...\n";cout << "Example 1: ";printResult(CheckTreeSumNonRecursive(root, 22)); // 输出 truecout << "Example 2: ";printResult(CheckTreeSumNonRecursive(root, 5)); // 输出 falsecout << "Example 3: ";printResult(CheckTreeSumNonRecursive(nullptr, 0)); // 输出 falsereturn 0;
}
http://www.lryc.cn/news/290517.html

相关文章:

  • 非阿里云注册域名如何在云解析DNS设置解析?
  • 微服务-微服务Alibaba-Nacos注册中心实现
  • 多符号表达式的共同子表达式提取教程
  • Java 反射获取属性名、属性类型、属性值、判断属性类型
  • Docker私有仓库搭建
  • C语言第十三弹---VS使用调试技巧
  • AST反混淆实战-jsjiamiv7最高配置
  • colorThief+vite+react使用方法
  • Hive(15)中使用sum() over()实现累积求和和滑动求和
  • 2024年Java搭建面试题
  • 二维数组的学习
  • Java集合(List集合)
  • 7、Json文件的操作总结【robot framework】
  • python 循环解压 解压多重压缩包
  • 基于C#制作一个连连看小游戏
  • Android-System 根据包名查找已安装应用apk方法
  • 洛谷-P4124题-手机号码-Java
  • 仅使用 Python 创建的 Web 应用程序(前端版本)第08章_商品详细
  • Stable Diffusion 长视频真人动画风格互转
  • 精要图示:园区金融数字化服务蓝图,以园区为支点推动信贷业务增长
  • 2024 中国(南京)国际口腔设备器械博览会
  • 【MyBatis】快速入门MyBatis(保姆式教学),你值得一看
  • git pull代码时候报错:error: cannot open .git/FETCH_HEAD: Permission denied
  • shell - 正则表达式和grep命令和sed命令
  • datawhale 大模型学习 第十二章-大模型环境影响
  • Qt WebEngine模块使用(开发环境安装和程序开发)
  • 网络体系结构 和网络原理之UDP和TCP
  • 将Android APP安装到sm8550 HDK的NVMe SSD
  • (Arcgis)Python编程批量将HDF5文件转换为TIFF格式并应用地理转换和投影信息
  • Linux:进度条的创建