Leetcode 112. Path Sum 二叉树中和为某一值的路径 Python3

方法 :递归
最直接的方法就是利用递归,遍历整棵树:如果当前节点不是叶子,对它的所有孩子节点,递归调用 hasPathSum 函数,其中 sum 值减去当前节点的权值;如果当前节点是叶子,检查 sum 值是否为 0,也就是是否找到了给定的目标和。

 

# 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: TreeNode, sum: int) -> bool:
        if root==None:
            return False
        
        if root.left ==None and root.right==None:
            return root.val==sum

        if self.hasPathSum(root.left,sum-root.val):
            return True
        
        if self.hasPathSum(root.right,sum-root.val):
            return True
        
        return False

 

Leetcode 112. Path Sum 二叉树中和为某一值的路径 Python3Leetcode 112. Path Sum 二叉树中和为某一值的路径 Python3 dragonfly91 发布了11 篇原创文章 · 获赞 3 · 访问量 5878 私信 关注
上一篇:nmap msf sqlmap


下一篇:Maven常用命令(转)