二进制树木遍历 - 递归

Question

在下面写下了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],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？

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]:

代码的问题在这里 -

1. 您添加了第三个参数， traversal_list ，默认值为<代码> []
2. 在代码的非恢复分支中，对此列表的引用
3. 在递归分支中返回， 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

reteation the问题

这意味着随后调用解决方案＃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                 #