c++中如何实现二叉树后序遍历非递归_c++二叉树后序非递归遍历方法

尼克

发布时间：2025-09-30 15:52:02

632人浏览过

来源于php中文网

原创

后序遍历非递归实现的关键是使用单栈配合last指针判断右子树是否已访问，先沿左路入栈，再根据右子树状态决定访问节点或转向右子树，最后更新last指针。

c++中如何实现二叉树后序遍历非递归_c++二叉树后序非递归遍历方法

在C++中实现二叉树的后序遍历非递归方式，关键在于模拟系统栈的行为，同时确保每个节点在左右子树都访问完毕后再处理自身。与前序和中序不同，后序遍历的非递归实现稍复杂，需要额外判断是否已经访问过子树。

使用单栈实现后序遍历（推荐方法）

核心思路是利用一个栈记录待处理的节点，并用一个指针记录上一次访问的节点，以此判断当前节点的右子树是否已访问。

从根节点开始，将所有“左路”节点入栈（类似中序遍历）
取栈顶节点，但不立即弹出，检查其右子树是否为空或已被访问
若满足条件，则访问该节点并弹出；否则进入右子树继续处理
用 last 指针记录最近访问的节点，避免重复进入右子树

代码实现如下：

```cpp #include #include using namespace std;

struct TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

void postorderTraversal(TreeNode* root) { if (!root) return;

stack stk;
TreeNode* last = nullptr;        // 记录上一个访问的节点
TreeNode* curr = root;

while (curr || !stk.empty()) {
    // 一路向左入栈
    while (curr) {
        stk.push(curr);
        curr = curr->left;
    }

    // 取栈顶，不弹出
    curr = stk.top();

    // 如果右子树为空，或右子树已访问过
    if (!curr->right || curr->right == last) {
        cout << curr->val << " ";
        stk.pop();
        last = curr;           // 更新最后访问节点
        curr = nullptr;        // 避免重复进入左子树
    } else {
        curr = curr->right;    // 进入右子树
    }
}

}

立即学习“C++免费学习笔记（深入）”；

DreamGen

一个AI驱动的角色扮演和故事写作的平台

下载

双栈法（易于理解）
另一种方法是使用两个栈：第一个栈按“根→右→左”的顺序压入节点，第二个栈用于反转输出顺序，最终得到“左→右→根”。


  先将根入栈1
  每次从栈1弹出节点，压入栈2，并依次将左、右孩子压入栈1
  最后依次弹出栈2，即为后序结果



代码示例：
```cpp
void postorderTwoStacks(TreeNode* root) {
    if (!root) return;

    stack stk1, stk2;
    stk1.push(root);

    while (!stk1.empty()) {
        TreeNode* node = stk1.top(); stk1.pop();
        stk2.push(node);

        if (node->left)  stk1.push(node->left);
        if (node->right) stk1.push(node->right);
    }

    // 输出栈2
    while (!stk2.empty()) {
        cout << stk2.top()->val << " ";
        stk2.pop();
    }
}

注意事项与技巧

单栈法空间效率更高，是面试常见写法。关键点在于 last 指针的使用，它解决了“如何判断右子树已访问”的问题。双栈法逻辑清晰，适合初学者理解后序的本质——逆前序的一种变形。

测试时建议构造如下树验证：
    1
  /   \
2     3
/
4
正确输出应为：4 2 3 1

基本上就这些，掌握单栈法足以应对大多数场景。

c++如何实现一个简单的内存池_c++高性能内存分配策略

c++怎么用C++为Node.js编写一个高性能模块_C++与Node.js模块开发实战

C++如何实现一个简单的哈希表_C++数据结构与哈希表实现

c++中如何使用结构体实现链表_c++结构体链表实现方法

c++怎么实现一个简单的A寻路算法_c++简单A寻路实现方法

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

node 栈 c++ if include 递归 int void 指针栈 using Struct Namespace

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++中的std::function怎么使用_c++ std::function使用方法下一篇：c++中如何合并两个数组_c++数组合并实现方法

作者最新文章

百度贴吧怎么看粉丝列表百度贴吧在哪查看谁关注了我【社交功能】

2026-01-25 11:41

Excel怎么制作动态图表 Excel点击切换展示数据方法【实例】

2026-01-25 11:47

c++如何用random_device生成真随机数_c++随机数引擎进阶【实战】

2026-01-25 11:48

sublime如何配置SQL数据库连接_sublime直接执行SQL语句教程【详解】

2026-01-25 11:51

c++中如何使用std::lexicographical_compare比较容器_c++技巧【汇总】

2026-01-25 11:52

Win11怎么关闭屏幕旋转 Win11锁定系统显示方向【显示】

2026-01-25 11:53

Win11怎么开启自动登录 Win11删除登录密码【便捷】

2026-01-25 11:53

C++ vector越界访问后果 C++缓冲区溢出攻击原理科普【安全】

2026-01-25 11:54

C++ string c_str怎么用 C++与C风格API兼容写法【兼容】

2026-01-25 11:57

Composer怎么解决依赖包410 Gone 资源已失效处理办法【排错】

2026-01-25 11:58

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PC软件

相关专题

if什么意思

if的意思是“如果”的条件。它是一个用于引导条件语句的关键词，用于根据特定条件的真假情况来执行不同的代码块。本专题提供if什么意思的相关文章，供大家免费阅读。

770

2023.08.22

string转int

在编程中，我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算，或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

381

2023.08.02

int占多少字节

int占4个字节，意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值，在某些情况下也可能是2个字节或8个字节，int是一种常用的数据类型，用于表示整数，需要根据具体情况选择合适的数据类型，以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

543

2024.08.29