二叉树的前序遍历（非递归实现）

二叉树的前序遍历顺序是根节点 → 左子树 → 右子树。递归实现非常简单但在实际应用中递归可能导致栈溢出树深度较大时因此掌握非递归版本是必要的。这里给出一种利用栈的迭代实现。算法思路模拟递归的执行过程。递归函数在调用时会隐式地将当前状态压入系统栈我们显式地使用一个栈来模拟这个行为。具体步骤从根节点开始沿着左子树一直向下走沿途访问每个节点并将其压入栈中。当左子树走到底当前节点为空时从栈中弹出一个节点表示该节点的左子树已经处理完毕接下来需要处理它的右子树。将当前指针指向弹出节点的右子树重复步骤1和2直到栈为空且当前指针也为空。这个过程中访问节点的时机是在节点入栈之前即第一次遇到节点时这正是前序遍历的定义。代码实现cppclass Solution { public: vectorint preorderTraversal(TreeNode* root) { vectorint result; stackTreeNode* stk; TreeNode* cur root; while (cur ! nullptr || !stk.empty()) { // 一直向左走访问并压栈 while (cur ! nullptr) { result.push_back(cur-val); // 访问当前节点根 stk.push(cur); // 入栈后续用来找右子树 cur cur-left; // 继续向左 } // 此时cur为空说明左子树走完弹出栈顶节点并转向其右子树 TreeNode* top stk.top(); stk.pop(); cur top-right; // 处理右子树 } return result; } };代码解释外层while循环控制整个遍历过程条件cur ! nullptr || !stk.empty()保证了当根节点为空或栈中还有待处理的节点时继续执行。内层while循环负责沿着当前节点的左链一直向下边移动边访问节点并将节点入栈。这对应了前序遍历先访问根、然后递归左子树的顺序。当内层循环结束时cur变为nullptr说明已经到达当前路径的最左端。此时栈顶节点是最后一个被访问的左路节点它的左子树已经处理完毕接下来需要处理它的右子树。所以我们弹出该节点并将cur指向它的右孩子开始下一轮循环。注意栈中保存的节点并不是为了再次访问它们因为已经访问过了而是为了在左子树完成后能找到它们的右子树入口。复杂度分析时间复杂度O(n)每个节点恰好被访问一次入栈一次出栈一次。空间复杂度O(h)h 为树的高度。最坏情况下树退化为链表空间复杂度 O(n)平均情况下为 O(logn)。与递归版本的对比递归版本代码更简洁cppvoid preorder(TreeNode* root, vectorint res) { if (!root) return; res.push_back(root-val); preorder(root-left, res); preorder(root-right, res); }但递归调用会使用系统栈深度过大时可能导致栈溢出。非递归版本显式使用栈可以更好地控制内存并且在某些语言如C中性能也可能更好。注意事项需要处理空树的情况此时直接返回空数组。循环条件中的cur和栈状态要正确理解当cur为空但栈不为空时说明还有右子树待处理当cur为空且栈也为空时遍历结束。内层循环的cur cur-left可能会导致空指针但外层循环已经处理了这种情况。扩展前序遍历的非递归实现是二叉树迭代遍历的基础类似的思想可以用于中序遍历访问时机改为出栈时和后序遍历需要更复杂的标记。理解这个模板有助于解决更多树相关的问题。