【代码随想录day19】路径总和_代码随想录求节点的路径和-CSDN博客

本文链接：https://blog.csdn.net/doubleguy/article/details/131918602

题目

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

叶子节点是指没有子节点的节点。

思路

一定要认真审题，题目说的是从根节点到叶子节点的路径，而我最开始以为只要里面有相加为target的就行，导致了一些错误。

其实整体思路比较简单，对于每一个节点，我们判断 它和target-root.val是否相等且是叶子节点 ，如果这样的节点存在，就说明找到了一条从根节点到叶子节点的路径且路径和为target。如果走到空节点都没找到，说明当前路径不是我们要找的，返回False。最后只要左子树或者右子树中的任意一个为True都算成功找到了。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def solve(root,target):
            if not root:
                return False
            if target==root.val and not root.left and not root.right:
                return True
            left = solve(root.left,target-root.val)
            right = solve(root.right,target-root.val)
            return left or right
        return solve(root,targetSum)

非递归方式

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def solve(root,target):
            if not root:
                return False
            stack = [(root, root.val)]
            while stack:
                now, path_sum = stack.pop()
                if path_sum==target and not now.left and not now.right:
                    return True
                if now.left:
                    stack.append((now.left, path_sum+now.left.val))
                if now.right:
                    stack.append((now.right, path_sum+now.right.val))
            return False
        return solve(root, targetSum)