03、前序遍历迭代

我们之前说了二叉树基础及二叉的几种遍历方式及练习题，今天我们来看一下二叉树的前序遍历非递归实现。

前序遍历的顺序是, 对于树中的某节点,先遍历该节点,然后再遍历其左子树,最后遍历其右子树.

我们先来通过下面这个动画复习一下二叉树的前序遍历。

前序遍历

前序遍历迭代

我们试想一下，之前我们借助队列帮我们实现二叉树的层序遍历，

那么可不可以，也借助数据结构，帮助我们实现二叉树的前序遍历。

见下图

image

假设我们的二叉树为 [1,2,3]。我们需要对其进行前序遍历。其遍历顺序为

当前节点 1，左孩子 2，右孩子 3。

这里可不可以用栈，帮我们完成前序遍历呢？栈和队列

我们都知道栈的特性是先进后出，我们借助栈来帮助我们完成前序遍历的时候。

则需要注意的一点是，我们应该先将右子节点入栈，再将左子节点入栈。

这样出栈时，则会先出左节点，再出右子节点，则能够完成树的前序遍历。

动画模拟

见下图。

我们用一句话对上图进行总结，当栈不为空时，栈顶元素出栈，如果其右孩子不为空，则右孩子入栈，其左孩子不为空，则左孩子入栈。还有一点需要注意的是，我们和层序遍历一样，需要先将 root 节点进行入栈，然后再执行 while 循环。

看到这里你已经能够自己编写出代码了，不信你去试试。

时间复杂度：O(n) 需要对所有节点遍历一次

空间复杂度：O(n) 栈的开销，平均为 O(logn) 最快情况，即斜二叉树时为 O(n)

代码

#include <vector>
#include <stack>

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    // 构造函数
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> result;  // 存储遍历结果
        std::stack<TreeNode*> stk;  // 辅助栈
        
        if (root == nullptr) {  // 空树直接返回空结果
            return result;
        }
        
        stk.push(root);  // 根节点入栈
        
        // 栈非空时循环
        while (!stk.empty()) {
            TreeNode* temp = stk.top();  // 获取栈顶节点
            stk.pop();  // 弹出栈顶节点
            
            // 前序遍历：根 -> 左 -> 右，栈是后进先出，故先压右子树再压左子树
            if (temp->right != nullptr) {
                stk.push(temp->right);
            }
            if (temp->left != nullptr) {
                stk.push(temp->left);
            }
            
            // 将当前节点值加入结果集
            result.push_back(temp->val);
        }
        
        return result;
    }
};