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

Question

我正试图编写代码，使用递归按顺序遍历二进制树，下面是我的代码：

例如，输入=[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'语句中的代码有关。有人能建议修改吗？感谢

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

对于以下二进制树

我想确保我正确理解它，递归堆栈将存储A，然后存储B，然后存储C。由于C没有子级(我们触及基本情况(。C然后被记录在CCD_ 3中。然后，我们从递归堆栈中弹出下一个项目，即B，此时我们调用inorderTraversal(root.left)还是inorderTraversal(root.right)？

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

Answer 1

有两个选项。您可以将一个数组传递到附加到的递归函数中，也可以返回一个数组并将其与调用函数的组合。第一种可能更具表演性，因为你没有一遍又一遍地移动相同的元素。但它并没有那么漂亮。使用上面的代码，这里有一个建议的更改。

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))