二叉树的遍历非递归c++

二叉树的遍历非递归实现需要使用栈来模拟递归过程。以下是C++的非递归实现代码：

前序遍历：

void preorderTraversal(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        // 访问节点
        visit(node);
        if (node->right) s.push(node->right);
        if (node->left) s.push(node->left);
    }
}

中序遍历：

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node || !s.empty()) {
        while (node) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        // 访问节点
        visit(node);
        node = node->right;
    }
}

后序遍历：

void postorderTraversal(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        TreeNode* node = s1.top();
        s1.pop();
        s2.push(node);
        if (node->left) s1.push(node->left);
        if (node->right) s1.push(node->right);
    }
    while (!s2.empty()) {
        TreeNode* node = s2.top();
        s2.pop();
        // 访问节点
        visit(node);
    }
}