AttributeError: 'NoneType' object has no attribute 'left'

Question

给定一棵二叉树和一个总和，确定该树是否有一条 root-to-leaf 路径使得沿路径的所有值相加等于给定的总和。

注：叶子是没有children.

的节点

示例：

给定下面的二叉树和 sum = 22，

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

return 正确，因为存在 root-to-leaf 路径 5->4->11->2 其总和为 22.

class Solution(object):
def hasPathSum(self, root, sum):
    """
    :type root: TreeNode
    :type sum: int
    :rtype: bool
    """
    l = []
    def helper(tree, total):
        if not tree.left and not tree.right:
            l.append(total)
        else:
            helper(tree.left, total + tree.val)
            helper(tree.right, total + tree.val)
        return l

    if root:
        helper(root, 0)
        return sum in l
    return False

谁能告诉我我的代码有什么问题？？？

Answer 1

主要问题是当节点的左侧或右侧 child 为 None 时，您的助手无法正确处理情况。它将在尝试访问 None.left 或 None.right.

时递归 children 和崩溃

除此之外，这里不需要列表；你可以 return True 如果你到达一片叶子并发现你的运行总数等于总和。这样效率更高，因为您避免在找到解决方案后遍历树的其余部分，并避免在树搜索结束后遍历列表以找到您的目标。

另外值得一提的是，Leetcode 给出了参数sum，它覆盖了一个内置函数。我通常会重命名这些变量，并冒昧地在这里这样做。

def hasPathSum(self, root, target):
    """
    :type root: TreeNode
    :type sum: int
    :rtype: bool
    """
    def helper(tree, total=0):
        if not tree.left and not tree.right:
            return target == total + tree.val

        if tree.left and helper(tree.left, total + tree.val):
            return True

        if tree.right and helper(tree.right, total + tree.val):
            return True

        return False


    return helper(root) if root else False

AttributeError: 'NoneType' object has no attribute 'left'

AttributeError: 'NoneType' object has no attribute 'left'

binary-tree

python-3.x