博客

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明:

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

示例:


给定如下二叉树，以及目标和

sum = 22

，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回

true

, 因为存在目标和为 22 的根节点到叶子节点的路径

5->4->11->2

。

思路：

DFS， 当扫描到叶节点时，如果和刚好为sum，就返回True。

class Solution(object):
    def hasPathSum(self, root, s):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        self.res = False
        
        def dfs(node, pathSum):
            if not self.res and node:
                pathSum += node.val
                
                if pathSum == s and not node.left and not node.right:
                    self.res = True
                    return
                
                dfs(node.left, pathSum)
                dfs(node.right, pathSum)
        dfs(root, 0)
        return self.res

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == sum
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)