下面寫了一個 leetcode 問題的解決方案https://leetcode.com/problems/binary-tree-inorder-traversal/ -
# 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
class Solution:
def inorderTraversal(self, root: Optional[TreeNode],traversal_list = []) -> List[int]:
if root:
traversal_list= self.inorderTraversal(root.left,traversal_list)
traversal_list.append(root.val)
traversal_list = self.inorderTraversal(root.right, traversal_list)
return traversal_list
從示例問題 #1 回傳 [1,3,2] 的正確解。從示例問題 #2：[ ] 再次回傳 [1,3,2]。
為什么答案 #1 會延續到問題 #2？
uj5u.com熱心網友回復：
不要修改引數的默認值
LeetCode 提供的模板——
# 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
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
您的代碼的問題在這里 -
- 您添加了第三個引數 ，
traversal_list其默認值為[] - 在代碼的非遞回分支中，回傳了對該串列的參考
- 在遞回分支中，
traversal_list被突變為.append
class Solution:
# ?? 1
def inorderTraversal(self, root: Optional[TreeNode],traversal_list = []) -> List[int]:
if root:
traversal_list= self.inorderTraversal(root.left,traversal_list)
traversal_list.append(root.val) # ?? 3
traversal_list = self.inorderTraversal(root.right, traversal_list)
return traversal_list # ?? 2
問題的再現
這意味著后續呼叫Solution#inorderTraversal將包含預填充traversal_list并導致錯誤答案。您可以在下面看到該問題的最小重現 -
def foo (x = []):
x.append(1)
return x
print(foo()) # [1]
print(foo()) # [1, 1] # ?
在另一個示例中，查看默認引數值如何在腳本執行時僅計算一次-
def hello():
print(1)
return 3
def foo (x = hello()): # ?? hello() happens first
return x
print(2) # ?? this is actually second!
print(foo())
1
2
3
修理它
要修復它，請洗掉第三個引數traversal_list. 沒有必要。不存在[]時只需回傳-root
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if root:
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
return left [root.val] right # ?
else:
return [] # ?
一種改進的撰寫方法是在類之外撰寫一個遍歷函式 -
def inorder(t):
if t:
yield from inorder(t.left) # ??
yield t.val # ??
yield from inorder(t.right) # ??
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
return list(inorder(root)) # ??
“如果我想使用附加怎么辦？”
如果您絕對想使用.append，您可以以類似的方式對上述解決方案進行建模。
def inorder(root):
output = [] # ??
def traverse(t):
if t:
traverse(t.left) # ??
output.append(t.val) # ?? ??
traverse(t.right) # ??
traverse(root)
return output # ??
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
return inorder(root) # ??
不是普遍的行為
請注意，此行為與其他語言直接對比。例如，JavaScript 會在每次運行函式時重新評估引數的默認值 -
function foo(x = []) {
x.push(1)
return x
}
console.log(foo()) // [1]
console.log(foo()) // [1] ?? differs from python's behaviourfunction hello() {
console.log(1)
return 3
}
function foo(x = hello()) {
return x
}
console.log(2)
console.log(foo())2
1 // ?? differs from python's behaviour
3
uj5u.com熱心網友回復：
類解決方案：
def inorderTraversal(self, root: Optional[TreeNode],traversal_list = []) -> List[int]:
print(root)
print('\n')
if not root:
return []
print(root.left)
if root.left:
yield from self.inorderTraversal(root.left)
yield root.val
print(root.right)
if root.right:
yield from self.inorderTraversal(root.right)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/470943.html