二叉树递归前序遍历代码原理解惑：为何能执行右子树递归调用？

我运行这段LeetCode上的二叉树递归前序遍历Python代码后确认其可通过所有测试用例，但对递归调用逻辑存在疑惑：不理解代码为何能执行preorder(node.right)这一行。我认为preorder(node.left)会持续递归，永远无法执行后续的右子树递归调用。我猜测当传入None时函数会直接返回，但不确定Python的具体执行逻辑，希望明确这段代码的运行原理。

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        out = []
        def preorder(node):
            if not node: return

            out.append(node.val)
            preorder(node.left)
            preorder(node.right)

            return

        preorder(root)
        return out

你的猜测完全正确，当传入None时，preorder函数会触发if not node: return直接返回，这就是递归的终止条件，也是代码能执行到右子树调用的核心原因。

我们拿一个简单的二叉树举例：根节点为A，左子节点是B，右子节点是C，B和C的左右子节点都是None，一步步拆解执行流程：

• 首先调用preorder(A)：A不为空，先把A的值加入out，接着执行preorder(B)。
• 进入preorder(B)：B不为空，把B的值加入out，接着执行preorder(B.left)（传入None）。
• 进入preorder(None)：触发终止条件，直接返回，回到preorder(B)的调用上下文，此时preorder(node.left)已经执行完毕，接下来会执行preorder(node.right)（同样传入None），执行后返回，preorder(B)整个函数执行完毕，回到preorder(A)的调用上下文。
• 此时preorder(node.left)（即preorder(B)）已经全部执行完，接下来会执行preorder(node.right)（也就是preorder(C)），重复类似流程：处理C的值，再依次调用C的左、右子树（都是None，直接返回），最后preorder(C)执行完毕，回到preorder(A)，整个递归流程结束。

核心逻辑是：每一次递归调用都有独立的执行上下文，当某个递归分支因终止条件返回后，程序会回到上一层调用的位置，继续执行后续代码。左子树的递归并不是无限进行，而是在遇到叶子节点的空孩子时终止，之后自然会回到父节点，继续处理右子树的递归。

内容的提问来源于stack exchange，提问作者pythontommi