前序/后序遍历递归机制疑问：Python执行逻辑与节点结构解析

一、递归遍历函数实现 #

前序遍历（PRE_ORDER_TRAVERSAL） #

def pre_order_traversal(root: Node):
    if root is not None:
        print(root.val)
        pre_order_traversal(root.left)
        pre_order_traversal(root.right)

后序遍历（POST_ORDER_TRAVERSAL） #

def post_order_traversal(root: Node):
    if root is not None:
        post_order_traversal(root.left)
        post_order_traversal(root.right)
        print(root.val)

二、疑问解答 #

• 后序遍历是否是通过递归调用root.left直至无左节点，再处理右节点，最后从调用栈弹出值打印？
  没错，递归版后序遍历就是这个逻辑。每次递归会先一路钻到当前分支的最左子节点，再处理该节点的右子树，等左右子树的遍历都完成后，才会执行当前节点的打印操作——这一步本质就是递归栈弹出时的动作：当子节点的递归调用全部结束，程序回到上一层函数，继续执行未完成的打印代码。

• Python如何控制树的层级遍历？
  Python靠调用栈自动管理递归层级。每发起一次递归调用，Python解释器会把当前函数的上下文（比如当前节点、执行到哪一行代码）压入栈中；当递归触底（比如遇到root为None），函数直接返回，栈顶的上下文弹出，程序回到上一层函数继续执行剩余逻辑（比如处理右子树、打印当前节点）。整个过程完全由解释器自动维护，不需要开发者手动干预。

• root.left的数据类型如何存储多个值？
  root.left本身是一个Node类的实例对象，不是直接存储多个值。每个Node对象会包含三个核心属性：val（当前节点的值）、left（指向左子节点的引用）、right（指向右子节点的引用）。所谓的“多值存储”是通过节点之间的引用关系串联实现的——比如节点4的left属性指向节点3，节点3的left和right又指向None（对应输入里的x），这样就形成了树的层级结构。

• 以输入“5 4 3 x x 8 x x 6 x x”为例，程序如何从节点4走到节点3？
  这个输入是前序序列化的二叉树，x代表空节点，解析后树的结构为：

  • 根节点5，左子节点4，右子节点6
  • 节点4的左子节点3，右子节点8
  • 节点3、8、6的左右子节点均为空

  当执行后序遍历到节点4时，会先调用post_order_traversal(root.left)——这里的root就是节点4，root.left是节点3。程序进入节点3的递归函数后：

  1. 检查节点3不为空，先调用它的left（是x/None），该调用直接返回；
  2. 再调用节点3的right（也是x/None），同样直接返回；
  3. 最后执行print(root.val)，打印3；
  4. 节点3的递归函数执行完毕，回到节点4的递归逻辑，接下来处理节点4的右子节点8，之后再打印4。

  这就是程序从节点4走到节点3并完成遍历的过程。

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