为什么这个解决方案起作用？Leetcode#94

Question

对于python我是新手，我正在做leetcode问题94，二叉树顺序遍历。给定二叉树的根，返回对其节点值的inorder遍历。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:return []
        res = []
        res+=self.inorderTraversal(root.left)
        res.append(root.val)
        res+=self.inorderTraversal(root.right)
        return res

但我还是不明白它为什么有用。在res.append(root.val)之后，在递归过程中，res变量不会被重新分配给[]吗res+=self.inordertraversal(root.right)？或者res变量在不同的递归中应该是不同的变量吗？

Answer 1

每个递归调用分配自己的本地res变量并返回它。最外层（第一个）res是通过组装（追加）内部/（更深层次）子问题的结果来构建的。

然而，我想指出的是，原始程序混合了遍历树和创建列表的问题。下面是inorder的一个实现，它只关注遍历-

def inorder(node):
  if not node: return
  yield from inorder(node.left)
  yield node.val
  yield from inorder(node.right)

要从iterable likeInOrder获取列表，我们使用list构造函数-

list(inorder(some_tree))
# => [ ... ]

关注点分离是成功程序员使用的基本技术。它使设计/编写函数变得更加容易，并促进代码重用。对于这个程序，这意味着你不仅仅局限于创建列表；在遍历树时，您可以执行任何操作，如搜索、创建新树、打印到stdout、写入文件或发出网络请求。

s = 0
for val in inorder(some_tree):
  print(f"node value: {val}")
  s += val
print(f"tree sum: {s}")

在类中包装所有内容来自Java和C#等语言，但在Python中没有任何好处。原始程序不是由一个流利的Python扬声器编写的另一个指示是使用了CamelCase而不是snake_case-

class solution:
  def inorder_traversal(self, root):
    return list(inorder(root))