个人主页：清风莫追
系列专栏：牛客刷题——数据结构与算法
推荐一款面试、刷题神器牛客网：👉点击开始刷题学习👈
1.题目描述
描述
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
- 该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
- 叶子节点是指没有子节点的节点
- 路径只能从父节点到子节点，不能从子节点到父节点
- 总节点数目为n
例如：
给出如下的二叉树，
s
u
m
=
22
sum=22
sum=22，
返回true，因为存在一条路径
5
→
4
→
11
→
2
5\to 4\to 11\to 2
5→4→11→2的节点值之和为 22。
数据范围：
1.树上的节点数满足
0
≤
n
≤
10000
0 \le n \le 10000
0≤n≤10000
2.每个节点的值都满足
∣
v
a
l
∣
≤
1000
|val| \le 1000
∣val∣≤1000
要求：空间复杂度
O
(
n
)
O
(
n
)
O(n)O(n)
O(n)O(n)，时间复杂度
O
(
n
)
O
(
n
)
O(n)O(n)
O(n)O(n)
进阶：空间复杂度
O
(
树的高度
)
O
(
树的高度
)
O(树的高度)O(树的高度)
O(树的高度)O(树的高度)，时间复杂度
O
(
n
)
O
(
n
)
O(n)O(n)
O(n)O(n)
2.算法设计思路
核心其实就是一个二叉树的遍历。可以采用回溯法，在遍历树的过程中，利用一个全局变量num记录遍历到当前节点时路径上所有值的和。
当以当前结点为根的子二叉树中没有符合要求的叶子结点时，就向上回溯（从父结点到子结点时，num的值增加了；因此返回时就减去相应的值。）
3.代码实现
注：这里并不是完整代码，而只是核心代码的模式
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
int num = 0;
bool hasPathSum(struct TreeNode* root, int sum ) {
// write code here
bool flag = false;
if(root == NULL){return false;}
num += root->val;
//printf("num:%d\n", num);
if(num == sum && root->left == NULL && root->right == NULL){return true;}
//查找左右子树
if(hasPathSum(root->left, sum) == true){return true;}
else {flag = true;}
if(hasPathSum(root->right, sum) == true){return true;}
else {flag = true;}
//回溯
if(flag == true){
num -= root->val;
return false;
}
//最后不加个返回，就会显示编译错误。其实前面逻辑上是一定会有返回值的
printf("error\n");
return false;
}
当没有最后一行代码return false;时，就会显示如下的编译错误，避坑（代码其实应该是没有问题的）。
4.运行结果
成功通过！
结束语：
今天的分享就到这里啦，快来加入刷题大军叭！
👉点击开始刷题学习👈
感谢阅读
个人主页：清风莫追
CSDN话题挑战赛第2期
参赛话题：学习笔记
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/114811.html
