LeetCode105 迭代版｜前序+中序重构二叉树（速度内存双99%，超详细拆解）
在二叉树算法题中，「根据前序和中序遍历序列重构二叉树」是经典高频题（LeetCode 105），主流解法有递归下标版和迭代栈版。递归版思路直观但存在递归栈开销，而迭代栈版能做到时间O(n)、空间O(n)最优，提交LeetCode可稳定实现速度和内存双99%+击败率，是面试中的“加分解法”。
本文将从「核心原理→代码逐行拆解→案例分步演示→优化亮点→常见误区」五个维度，手把手讲解迭代版代码的每一个细节，保证新手也能看懂、会写、能复用，文末附可直接提交的完整代码和扩展思路。
一、前置知识：前序+中序遍历的核心规律
重构二叉树的前提是吃透两种遍历的顺序特性，这是迭代思路的根基，务必牢记：
前序遍历（Preorder）：根节点 → 左子树 → 右子树（特点：第一个元素永远是当前树/子树的根节点，后续元素先连续遍历左子树，再遍历右子树）；
中序遍历（Inorder）：左子树 → 根节点 → 右子树（特点：根节点左侧全是左子树节点，右侧全是右子树节点，可作为“判断左子树是否遍历完毕”的参照物）。
核心观察：前序遍历的“先左后右”，与中序遍历的“左→根→右”存在强关联——前序中连续的“左子树节点”，在中序中一定是从左到右连续排列在根节点左侧，当中序遍历到根节点时，说明当前根的左子树已全部遍历完毕，接下来该处理右子树。
二、迭代版核心思路
迭代版的核心是「用栈模拟递归的“向下钻左子树、回溯找右子树”过程」，搭配一个中序指针，判断当前节点该挂在左还是右，全程不使用哈希表、不切割数组、不拷贝元素，最大化节省内存。
整体思路可总结为3步，记牢口诀就能吃透：
初始化：前序第一个元素为整棵树的根节点，入栈；中序指针从最左侧开始（inIdx=0），用于匹配左子树是否遍历完毕；
遍历前序剩余元素：逐个生成当前节点，判断栈顶节点与中序指针指向的元素是否相等；
不相等：说明还在左子树区间，将当前节点挂为栈顶节点的左孩子，入栈继续往下钻；
相等：说明左子树已遍历完毕，回溯出栈（直到栈顶与中序指针元素不相等），将当前节点挂为最后一个出栈节点的右孩子，入栈；
循环结束，返回根节点，整棵树构建完成。
关键逻辑：栈的作用是“记录当前遍历路径上的根节点”，中序指针的作用是“判断左子树是否结束，何时开始处理右子树”，两者配合实现无递归、无额外开销的建树。
三、完整代码（可直接提交，双99%最优）
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty()) return nullptr;
TreeNode* root = new TreeNode(preorder[0]);
stack<TreeNode*> st;
st.push(root);
int inIdx = 0;
for (int i = 1; i < preorder.size(); ++i)
{
TreeNode* cur = nullptr;
TreeNode* node = new TreeNode(preorder[i]);
// 沿着左子树一直往下
if (!st.empty() && st.top()->val != inorder[inIdx])
{
st.top()->left = node;
}
else
{
// 匹配到中序，回溯找右父节点
while (!st.empty() && st.top()->val == inorder[inIdx])
{
cur = st.top();
st.pop();
inIdx++;
}
cur->right = node;
}
st.push(node);
}
return root;
}
};
四、代码逐行拆解（重点+难点详解）
以下按代码执行顺序，拆解每一行的作用，重点讲解容易踩坑的细节，帮你避开新手误区。
1. 边界条件处理
if (preorder.empty()) return nullptr;
当输入的前序（或中序）数组为空时，说明是空树，直接返回nullptr。这里不用判断inorder.empty()，因为前序和中序数组长度一定相等（题目保证输入有效），前序为空则inorder也为空。
2. 根节点初始化与栈准备
TreeNode* root = new TreeNode(preorder[0]); stack<TreeNode*> st; st.push(root); int inIdx = 0;
前序第一个元素必然是整棵树的根节点，新建根节点后入栈；
栈的作用：记录当前“正在遍历的路径”，栈内元素都是未处理完右子树的根节点；
inIdx（中序指针）：从0开始，指向中序数组的最左侧，代表“当前待匹配的左子树最后一个节点”。
3. 遍历前序剩余节点（核心循环）
for (int i = 1; i < preorder.size(); ++i)
i从1开始，因为前序第一个元素（i=0）已经作为根节点处理完毕，后续元素都是左子树或右子树的节点。
4. 当前节点创建与挂载判断
TreeNode* cur = nullptr; TreeNode* node = new TreeNode(preorder[i]);
node：当前要挂载到树上的节点（前序遍历到的下一个节点）；
cur：用于记录“回溯时，能挂载右孩子的父节点”，初始化为nullptr，只有进入回溯逻辑时才会赋值。
5. 核心判断：挂左孩子还是右孩子
if (!st.empty() && st.top()->val != inorder[inIdx]) { st.top()->left = node; } else { // 回溯逻辑 while (!st.empty() && st.top()->val == inorder[inIdx]) { cur = st.top(); st.pop(); inIdx++; } cur->right = node; }
这是整个代码的灵魂，分两种情况详解：
情况1：栈顶节点 != 中序当前节点（挂左孩子）
说明当前还在「左子树遍历区间」——前序遍历的当前节点（node），是栈顶节点的左孩子。比如前序[3,9,20]，中序[9,3,20]，当i=1（node=9）时，栈顶是3，3 != inIdx=0指向的9，所以9挂为3的左孩子。
为什么？因为前序先遍历左子树，中序先遍历左子树，此时中序指针还没走到根节点（3），说明左子树还没遍历完，当前节点必然是左孩子。
情况2：栈顶节点 == 中序当前节点（挂右孩子，回溯逻辑）
说明当前栈顶节点的「左子树已经全部遍历完毕」——中序指针指向的节点，就是栈顶节点的左子树最后一个节点，此时需要回溯，找能挂载右孩子的父节点。
回溯循环的作用：不断出栈，直到栈顶节点与中序当前节点不相等（或栈空），期间记录最后一个出栈的节点（cur），这个cur就是“需要挂右孩子的父节点”。
举个例子：前序遍历到20（i=2）时，栈顶是9，9 == inIdx=0指向的9，进入回溯：出栈9，inIdx++（变为1）；此时栈顶是3，3 == inIdx=1指向的3，继续出栈3，inIdx++（变为2）；栈空，回溯结束，cur=3，将20挂为3的右孩子。
6. 当前节点入栈
st.push(node);
无论当前节点挂在左还是右，都要入栈——因为它可能是后续节点的父节点（后续节点可能是它的左/右孩子），栈需要保持“当前遍历路径”的记录。
7. 返回根节点
return root;
循环结束后，整棵树构建完成，根节点始终是最初创建的root，直接返回即可。
五、案例分步演示（直观理解每一步）
用经典测试用例，一步步演示代码执行过程，帮你彻底吃透逻辑（建议对照代码看）：
测试用例：
前序（preorder）：[3,9,20,15,7]
中序（inorder）：[9,3,15,20,7]
步骤1：初始化
root = new TreeNode(3)，栈st=[3]，inIdx=0，i从1开始。
步骤2：i=1，node=9
栈顶3 != inorder[0]=9 → 3的左孩子=9，st.push(9) → 栈st=[3,9]。
步骤3：i=2，node=20
栈顶9 == inorder[0]=9 → 进入回溯：
cur=9，st.pop() → 栈st=[3]，inIdx=1；
栈顶3 == inorder[1]=3 → cur=3，st.pop() → 栈st为空，inIdx=2；
回溯结束，cur=3的右孩子=20，st.push(20) → 栈st=[20]。
步骤4：i=3，node=15
栈顶20 != inorder[2]=15 → 20的左孩子=15，st.push(15) → 栈st=[20,15]。
步骤5：i=4，node=7
栈顶15 == inorder[2]=15 → 进入回溯：
cur=15，st.pop() → 栈st=[20]，inIdx=3；
栈顶20 == inorder[3]=20 → cur=20，st.pop() → 栈st为空，inIdx=4；
回溯结束，cur=20的右孩子=7，st.push(7) → 栈st=[7]。
步骤6：循环结束，返回root
最终构建的树：
与预期完全一致，无任何错误。
六、优化亮点（为什么能双99%击败）
对比递归版、哈希表版，这个迭代版的优势非常明显，也是面试中推荐写法的核心原因：
零额外数组拷贝：不切割vector（避免每次递归新建vector的内存开销），全程复用原数组，内存占用极低；
无哈希表：不用提前存储中序元素的下标（避免哈希表的内存占用和寻址冲突），用中序指针+栈回溯实现匹配，时间更稳定；
无递归开销：递归会产生栈帧开销，迭代用系统栈模拟，开销更小，速度更快；
时间复杂度O(n)：前序遍历一次（n个节点），中序指针线性移动一次（n步），栈的入栈出栈总次数O(n)，整体线性时间；
空间复杂度O(n)：栈最多存储n个节点（最坏情况，比如左斜树），但这是必须的开销，无额外冗余空间。
七、常见误区
误区1：忘记将当前节点入栈 → 后续节点无法挂载到它的左/右孩子，导致树构建不完整；
误区2：回溯时不移动inIdx → 会导致无限循环（栈顶始终等于中序当前节点，一直出栈）；
误区3：cur未初始化或回溯后未判断cur是否为空 → 极端情况（比如树只有右子树）会导致空指针崩溃；
误区4：i从0开始遍历前序 → 根节点被重复处理，导致树结构错误。
八、扩展思路（举一反三）
学会这个迭代思路后，可直接迁移到其他二叉树构造题，比如：
后序+中序重构二叉树：思路完全一致，只是前序遍历顺序改为“左→右→根”，调整遍历顺序和回溯逻辑即可；
验证二叉树的前序/中序遍历有效性：复用“栈+中序指针”的思路，判断遍历序列是否符合二叉树的遍历规律；
二叉树的迭代版遍历：本质是同一个栈模拟思路，只是不新建节点，只记录遍历顺序。
九、总结
迭代版前序+中序重构二叉树，核心是「用栈模拟递归路径，用中序指针判断左子树边界」，全程无额外冗余开销，是速度和内存双优的最优解。
记住核心口诀：前序一路往左压栈，遇上中序相等就回溯，回溯完了挂右娃，就能轻松写出代码。