LeetCode 112. Path Sum路径总和 (C++)
2024-09-06 10:05:27
题目:
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Note: A leaf is a node with no children.
Example:
Given the below binary tree and sum = 22
,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2
which sum is 22.
分析:
给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。
从根节点判断是否存在一条到叶子节点的路径和等于目标和,等同于判断根节点的左右节点到叶子节点的路径和等于目标和减去根节点的值。
从给的例子中来看,判断根节点5是否有路径和等于22,相当于判断根节点的左节点4是否有路径和等于22减去5,也就是17,继续计算下去,11的时候判断是否有路径和等于13,其左叶子节点等于7,不等于13-11,而右叶子节点为2,等于13-11,返回true。
程序:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if(root == nullptr) return false;
if(root->left == nullptr && root->right == nullptr && root->val == sum)
return true;
return hasPathSum(root->left, sum-root->val)||hasPathSum(root->right, sum-root->val);
}
};
最新文章
- springmvc<;一>;一种资源返回多种形式【ContentNegotiatingViewResolver】
- Brackets(bestcoder)
- Request.InputStream 接收Post Data
- (部署新java程序,程序报错,需copy的一个包)——java使用siger 获取服务器硬件信息
- HTTP 笔记与总结(5)socket 编程:使用 HTTP 协议模拟登录并发帖
- ext3文件系统基础
- [转]解决crystal report水晶报表在浏览器提示bobj未定义的错误
- python3-day3(深浅copy)
- hdu1853解题报告
- linux系统编程快速定位头文件的技巧之强大的grep命令
- 关于input内容改变的触发时间
- 如何优雅的运行起jmeter
- 模拟setTimeOut
- 论文笔记:Visual Semantic Navigation Using Scene Priors
- vuejs实现瀑布流布局(二)
- 我一直跑的分类LSTM模型原来是这一个,新闻分类网络
- 沟通修炼 I型沟通->;U型沟通
- java基础-引用数据类型之二维数组(Array)
- Inf2Cat应用的参数使用详细介绍
- [转] 深入理解Java G1垃圾收集器