leetcode 112. 路径总和(python)

╰半橙微兮° 2022-05-19 10:27 214阅读 0赞

**【前言】**

python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]

github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

**【正文】**

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

**说明:** 叶子节点是指没有子节点的节点。

**示例:**   
给定如下二叉树，以及目标和 `sum = 22`，

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

返回 `true`, 因为存在目标和为 22 的根节点到叶子节点的路径 `5->4->11->2`。

--------------------

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
     
    class Solution:
        def hasPathSum(self, root, sum):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: bool
            """
            if root == None:
                return False
            if root.left == None and root.right == None:
                return sum == root.val
            elif root.right == None and root.left != None:
                return self.hasPathSum(root.left, sum-root.val)
            elif root.left == None and root.right != None:
                return self.hasPathSum(root.right, sum-root.val)
            else:
                return self.hasPathSum(root.left, sum-root.val) or \
                       self.hasPathSum(root.right, sum-root.val)

[https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[https_github.com_Teingi_test]: https://github.com/Teingi/test