为什么我遍历二叉树in-order的代码只记录第一个节点的值？

Question

我正在尝试编写代码来使用递归遍历二叉树 in-order，这是我的代码：

例如输入 = [1,null,2,3]

# 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: TreeNode) -> List[int]:
        in_order = []
        stack, curr = [], root

        if not curr: 
            return None
        else:
            inorderTraversal(curr.left)
            in_order.append(curr.val)
            inorderTraversal(curr.right)

        return in_order

由于某些原因，输出只记录了第一个节点的值！所以我得到 in_order=[1] 我怀疑它与 'else' 语句中的代码有关。谁能建议修改？谢谢

作为后续，基于提供的解决方案：

以下Binary tree

我想确保我理解正确，递归堆栈将存储 A，然后是 B，然后是 C。因为 C 没有 child（我们遇到了基本情况）。然后将C记录在in_order中。然后我们从递归堆栈中弹出下一个项目 B，此时我们调用 inorderTraversal(root.left) 还是 inorderTraversal(root.right)？

更一般地说，当我们从递归堆栈中弹出东西时，我们是否从第一个递归调用开始向下工作？计算机是如何处理的？我了解 objects 是如何添加到递归堆栈的，但令人困惑的是当它们被弹出时，我们从哪里开始？因为我读它的方式是保存 A、B、C 的递归堆栈来自 inorderTraversal(root.left)，所以这意味着当它们被弹出时我们应该向下移动到下一行 in_order.append(root.val)；这样对吗？

Answer 1

对此有两种选择。您可以将数组传递到您附加的递归函数中。或者您可以 return 一个数组并将其与调用函数的组合。第一个可能性能更高，因为您不会一遍又一遍地移动相同的元素。但它并不那么漂亮。使用上面的代码，这里有一个建议的更改。

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

        return in_order

更新

要遍历 OP 中的树，以下是调用的样子。为了简洁起见，我将缩短对 R() 的函数调用，我将简单地通过它的值来引用树。缩进将象征递归堆栈的深度。

R(A)
  R(B) # A.left
     R(C) # B.left
        R(C.left)
           return []
        Append(C)
        R(.right)
           return []
        return [C]    # R(C.left) + [C] + R(C.right)
     Append(B)
     R(D) # B.right
        R(E)  # D.left
        Append(D)
        R(D.right)  
           return []
        return [E, D]      # R(D.left) + [D] + R(D.right)
     return [C, B, E, D]   # R(B.left) + [B] + R(B.right)
  Append(A)
  R(G)  # A.right
      ...

   return [C, B, E, D, A, F, G, H]  # R(A.left) + [A] + R(A.right)

Answer 2

您没有使用递归调用的结果（常见错误）。另一个答案已经涵盖了这一点。您可以使用生成器函数非常优雅地完成此操作，但是：

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        def io(node):
            if node: 
                yield from io(node.left)
                yield node.val
                yield from io(node.right)

        return list(io(root))

为什么我遍历二叉树in-order的代码只记录第一个节点的值？

Why is my code to traverse binary tree in-order only recording the value of the first node?

python

tree

recursion