112。路径和题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/path-sum题目给定一棵二叉树和一个目标和，判断树是否存在从根节点到叶子节点的路径在中，这条路径上所有节点值的总和等于目标总和。解释：叶节点是指没有子节点的节点。例子：给定如下二叉树，并且目标和=22,5/\48//\11134/\\721返回真，因为从根节点有一条路径目标和为22到叶节点5->4->11->2。解题思路：递归与广度优先搜索这里先说递归。这个解法的思路是从根节点往下看，找到叶子节点。先假设根节点到当前节点的路径之和为val，然后换个问题，是否可以求出当前节点到叶子节点的路径之和为sum-val，符合递归的本质。也就是说，从根节点往下找叶子节点。如果判断当前节点是叶子节点，则判断sum是否等于当前节点的val值。如果不是叶子节点，则继续往下看。具体代码实现见【代码实现#递归】同题，我们也可以使用广度优先搜索的思想来求解。这里我们使用了一个队列，它存储了从根节点到某个节点的节点和路径的总和。以题中给出的例子为例，具体实现过程如下图所示：具体实现代码见【代码实现#广度优先搜索】代码实现#递归#二叉树节点的定义。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defhasPathSum(self,root:TreeNode,sum:int)->bool:if不是root：如果不是root.left也不是root.right，则返回False：返回sum==root.val返回self.hasPathSum(root.left,sum-root.val)或self.hasPathSum(root.right,sum-root.val)#广度优先搜索#二叉树节点的定义。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defhasPathSum(self,root:TreeNode,sum:int)->bool:ifnotroot:returnFalsefromcollectionsimportdeque#队列存储节点和路径queue=deque()queue.append((root,root.val))whilequeue:#出列，开始搜索节点，path=queue.popleft()#如果叶子节点和path之和等于目标值，直接返回Trueifnotnode.leftandnotnode.rightandpath==sum:returnTrueifnode.left：队列。append((node.left,path+node.left.val))ifnode.right:queue.append((node.right,path+node.right.val))returnFalse实现结果递归广度优先搜索文章原创，欢迎关注点赞微信公众号《书所集录》同步更新，也欢迎关注交流。
