二叉树路径总和（python）

请检查我的代码。我找不到错误在哪里。问题是here。二叉树路径总和（python）

这里是我的解决方案：

# Given a binary tree, find all paths that sum of the nodes in the path equals to a given number target. 
# 
# A valid path is from root node to any of the leaf nodes. 

# Example 
# Given a binary tree, and target = 5: 
# 
#  1 
# /\ 
# 2 4 
# /\ 
# 2 3 
# return 
# 
# [ 
# [1, 2, 2], 
# [1, 4] 
# ] 



class TreeNode: 
    def __init__(self, x): 
     self.val = x 
     self.left = None 
     self.right = None 

class Solution: 
    # @param {TreeNode} root the root of binary tree 
    # @param {int} target an integer 
    # @return {int[][]} all valid paths 

    result = [] 

    def binaryTreePathSum(self, root, target): 
     # Write your code here 
     if root is None: 
      return self.result 
     self.dfs(root, [], target) 
     return self.result 

    def dfs(self, node, tmp, target): 
     tmp.append(node.val) 
     if node.left is None and node.right is None: 
      if target == sum(tmp): 
       #print tmp 
       self.result.append(tmp) 
      tmp.pop() 
      return 

     if node.left: 
      self.dfs(node.left, tmp, target) 
     if node.right: 
      self.dfs(node.right, tmp, target) 
     tmp.pop() 

if __name__ == "__main__": 
    root = TreeNode(1) 
    root.left = TreeNode(2) 
    root.left.left = TreeNode(2) 
    root.left.right = TreeNode(3) 
    root.right = TreeNode(4) 
    result = Solution().binaryTreePathSum(root, 5) 
    print result

我们假设输入为{1,2,4,2,3}, 5。运行该解决方案后，输出为[[],[]]。但是，如果我取消缩进了print tmp，输出将是

[1, 2, 2] 
[1, 4] 
[[],[]]

的tmp输出是正确的。但似乎result.append(tmp)没有将tmp附加到result。我不知道问题在哪里。

来源

2017-05-26 Bramble

1.我看不到你的“问题”，因为我没有lintcode帐户，我不愿意创建一个。 2.什么是'{1,2,4,2,3}'？这应该是一组？因为如果它是一个集合，它就等于'{1,2,3,4}'。 3. *“假设输入是......”*输入_what_？如果你将这些参数传递给'binaryTreepathSum'，它会抛出一个AttributeError。 –

请__填写完整的代码___（不要让人们讨论你要做的事情）。检查[\ [SO \]：MCVE]（https://stackoverflow.com/help/mcve）或[\ [SO \]：如何问]（https://stackoverflow.com/help/how-to-问）。无论如何，它应该是简单的东西（对于缩进缺乏抱歉，但它不可能在注释中）：'def tree_sum（tree）：if tree is None：return 0 else：return tree.val + tree_sum（tree.left）+ tree_sum（tree.right）'。 – CristiFati

对不起，我添加了完整的代码和问题描述。 – Bramble

问题是您的result列表包含一个和相同的列表多次。

要追加的tmp列表result像这样：

self.result.append(tmp)

然后你就突变所同样的清单，tmp.pop()和tmp.append(...)。这就是为什么最后，所有结果都是空白列表。

解决方法很简单，只需创建列表的副本：

self.result.append(tmp[:])

来源

2017-05-26 11:06:32

酷！这个问题困扰了我三个小时。谢谢你让我摆脱酷刑:) – Bramble

二叉树路径总和（python）

回答

相关问题