力扣112.路径总和
2026-05-04 08:19:42
一、题目描述：
给你二叉树的根节点root和一个表示目标和的整数targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和targetSum。如果存在，返回true；否则，返回false。
叶子节点是指没有子节点的节点。
示例1：
输入：root=[5,4,8,11,null,13,4,7,2,null,null,null,1],targetSum=22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。
示例2：
输入：root=[1,2,3],targetSum=5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1-->2):和为3
(1-->3):和为4
不存在sum=5的根节点到叶子节点的路径。
示例3：
输入：root=[],targetSum=0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
树中节点的数目在范围[0,5000]内
-1000<=Node.val<=1000
-1000<=targetSum<=1000
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/path-sum著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
这道题考察了什么思想？你的思路是什么？
这道题目本质上就是二叉树的遍历，不过需要在遍历时对路径进行求和，需要防止重复计算。
我们需要先判断根节点是否为空，如果为空，根据示例3，也是返回false，由于树是空的，所以不存在根节点到叶子节点的路径。
如果根节点只有一个根节点，就直接比较根节点的值与参数sum即可。
不然，我们就递归判断，我们每次递归每个节点的左右节点，并减去每个节点的val值，上面也是递归结束的条件。
做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？
是一次通过的。需要注意递归退出条件以及节点为空时的情况。
有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？
/***Definitionforabinarytreenode.*structTreeNode{*intval;*structTreeNode*left;*structTreeNode*right;*};*/boolhasPathSum(structTreeNode*root,intsum){if(root==NULL){returnfalse;}if(root->left==NULL&&root->right==NULL){returnsum==root->val;}returnhasPathSum(root->left,sum-root->val)||hasPathSum(root->right,sum-root->val);}还有大佬写的BFS：
typedefstructqueNode{intval;structTreeNode*node;structqueNode*next;}queNode;voidinit(structqueNode**p,intval,structTreeNode*node){(*p)=(structqueNode*)malloc(sizeof(structqueNode));(*p)->val=val;(*p)->node=node;(*p)->next=NULL;}boolhasPathSum(structTreeNode*root,intsum){if(root==NULL){returnfalse;}structqueNode*queLeft,*queRight;init(&queLeft,root->val,root);queRight=queLeft;while(queLeft!=NULL){structTreeNode*now=queLeft->node;inttemp=queLeft->val;if(now->left==NULL&&now->right==NULL){if(temp==sum)returntrue;}if(now->left!=NULL){init(&queRight->next,now->left->val+temp,now->left);queRight=queRight->next;}if(now->right!=NULL){init(&queRight->next,now->right->val+temp,now->right);queRight=queRight->next;}queLeft=queLeft->next;}returnfalse;}作者：LeetCode-Solution链接：https://leetcode.cn/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。三、AC代码：
同上。
四、总结：
题目链接：112.路径总和
这道题目需要多刷刷几次，递归方法要掌握，建议二刷。
原文：https://juejin.cn/post/7101648070361743396热门标签
