如何以非递归方式由中序与前序遍历序列构建二叉树？

阿华AIGC实验室

2026-5-15

非递归方式从先序+中序遍历重构二叉树

咱们直接用你给出的例子来拆解非递归实现的思路，这样更清晰：
给定节点集合：1 2 3 4 5 6 7 8 9

中序遍历：4,2,5,8,1,6,3,9,7
前序遍历：1,2,4,5,8,3,6,7,9

核心思路回顾

递归实现的核心是：前序的第一个元素是子树的根，中序中根左边是左子树，右边是右子树。非递归实现的关键就是用栈模拟递归的调用栈，同时记录每个节点的子树边界，避免递归的函数调用开销。

具体步骤（结合例子）

1. 预处理：建立中序索引映射

先把中序遍历的每个节点值和它的索引存在哈希表里，这样能O(1)时间定位节点在中序中的位置，快速判断子树范围。
比如例子中的映射：
inorder_map = {4:0, 2:1, 5:2, 8:3, 1:4, 6:5, 3:6, 9:7, 7:8}

2. 初始化栈和指针

前序第一个元素1是整棵树的根，创建根节点。
栈中存储**(当前节点, 子树中序左边界, 子树中序右边界)**，初始栈为[(root节点, 0, 8)]（0和8是整个中序序列的首尾索引）。
用pre_ptr指针从1开始遍历前序序列（第一个元素已经用来创建根了）。

3. 遍历前序序列，逐个构建节点

循环处理每个前序元素，直到遍历完成：

情况1：当前元素是栈顶节点的左孩子：如果当前元素的中序索引 < 栈顶节点的中序索引，说明它是栈顶的左子节点。创建节点并挂载为栈顶的左孩子，然后把这个新节点和它的子树边界（原左边界到栈顶节点索引-1）压入栈，指针右移。
情况2：当前元素是某个祖先的右孩子：如果当前元素的中序索引 > 栈顶节点的中序索引，说明栈顶节点的左子树已经处理完，需要弹出栈顶，直到找到一个节点，它的中序索引 < 当前元素的中序索引 ≤ 该节点的右子树边界。此时当前元素就是这个节点的右孩子，创建节点挂载后压入栈，指针右移。

用例子走一遍关键步骤：

初始栈：[(1,0,8)]，pre_ptr=1（对应元素2）。2的中序索引1 < 1的索引4，所以2是1的左孩子，栈变为[(1,0,8), (2,0,3)]，pre_ptr=2。
下一个元素4，索引0 < 2的索引1，是2的左孩子，栈更新，pre_ptr=3。
元素5，索引2 > 4的索引0，弹出4；此时栈顶是2，5的索引2 > 2的索引1且 ≤ 2的右边界3，所以5是2的右孩子，栈更新，pre_ptr=4。
后续元素以此类推，直到所有节点都挂载完成。

可运行的Python代码实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    # 预处理中序索引，快速定位节点位置
    inorder_map = {val: idx for idx, val in enumerate(inorder)}
    root = TreeNode(preorder[0])
    # 栈元素：(当前节点, 中序左边界, 中序右边界)
    stack = [(root, 0, len(inorder) - 1)]
    pre_ptr = 1
    
    while pre_ptr < len(preorder):
        curr_node, in_left, in_right = stack[-1]
        curr_val_idx = inorder_map[curr_node.val]
        pre_val = preorder[pre_ptr]
        pre_val_idx = inorder_map[pre_val]
        
        if pre_val_idx < curr_val_idx:
            # 构建左孩子
            left_child = TreeNode(pre_val)
            curr_node.left = left_child
            stack.append((left_child, in_left, curr_val_idx - 1))
            pre_ptr += 1
        else:
            # 弹出栈顶，寻找右孩子的父节点
            stack.pop()
            found_parent = False
            while stack:
                parent, p_left, p_right = stack[-1]
                parent_val_idx = inorder_map[parent.val]
                if parent_val_idx < pre_val_idx <= p_right:
                    # 找到合适的父节点，构建右孩子
                    right_child = TreeNode(pre_val)
                    parent.right = right_child
                    stack.append((right_child, parent_val_idx + 1, p_right))
                    pre_ptr += 1
                    found_parent = True
                    break
            # 极端情况：整棵树只有右子树（例子中不会出现）
            if not found_parent:
                right_child = TreeNode(pre_val)
                curr_node.right = right_child
                stack.append((right_child, curr_val_idx + 1, in_right))
                pre_ptr += 1
    return root