二叉树中序遍历 - 递归

Question

下面写了一个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

Returns 示例问题 #1 中 [1,3,2] 的正确解。 Returns [1,3,2] 再次来自示例问题 #2：[ ].

为什么答案 #1 会转移到问题 #2？

Answer 1

不要修改参数的默认值

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，默认值为 []
在代码的 non-recursive 分支中，对该列表的引用是 returned
在递归分支中，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 不存在时，只需 return [] -

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 [] # ✅

一种改进的写法是在 class -

之外写一个遍历函数

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 将 re-evaluate 一个参数的默认值

function foo(x = []) {
  x.push(1)
  return x
}

console.log(foo()) // [1]
console.log(foo()) // [1]  differs from python's behaviour

function 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

Answer 2

class 解法：

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)

二叉树中序遍历 - 递归

Binary Tree Inorder Traversal - Recursive

python

recursion

binary-tree