二叉樹路徑總和（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）

回答

相關問題