时间戳

首页 > 解决方案 > leetcode 中的“路径总和”算法有什么问题？

python - leetcode 中的“路径总和”算法有什么问题？

问题描述

我正在练习 leetcode，但陷入了一项测试，无法找出我的错误。任何帮助将不胜感激。

问题：给定二叉树的根和一个整数 targetSum，如果树具有从根到叶的路径，使得沿路径的所有值相加等于 targetSum，则返回 true。

叶是没有子节点的节点。

示例 1：在此处输入图像描述

# 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
from collections import deque 
#code starts from here
class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        stack = collections.deque()
        sum1 = 0
        while(1):
            while(root != None):
                stack.append(root)
                sum1 = sum1 + root.val
                
                root = root.left
            if(sum1 == targetSum):
                return("true")
            
            if(root):
                root = stack.pop()
                sum1 = sum1 - root.val
                root = root.right
            else:
               
                break
            
        return("false")

我的代码落在这个测试用例上：

[1,2,3]
5

失败的测试用例场景

标签： pythonpython-3.xalgorithm

解决方案

让我们手动浏览您的代码。我将使用连字符来表示每个变量在执行期间给定点的状态。

  First iteration of outer while loop:
  - stack (top -> bottom = left -> right) = empty
  - sum1 = 0
  - root = node 1
    First iteration of inner while loop:
      stack.append(node 1)
      sum1 = 0 + 1 = 1
      root = node 1.left = node 2
    Second iteration of inner while loop:
      stack.append(node 2)
      sum1 = 1 + 2 = 3
      root = node 2.left = None (break)
  - stack = node 2, node 1
  - sum1 = 3
  - root = None
    sum1 == 5 is false, so do not return "true"
    root = None, break
  Outside while loop
    return "false"

好吧，您的代码返回了字符串“false”，但预期的布尔值 false。您需要修复的一个更令人担忧的错误是只会检查左侧路径。您需要更改内部 while 循环的逻辑。

例如，您会注意到以下测试用例：

[1, 2, 3]
4

即使正确的路径总和为 4，您的代码也会返回 false（假设您修复了返回类型错误）。这是因为仅遍历了左侧路径 (1, 2)。

推荐阅读