文档章节

非递归后序遍历二叉树

LeotyLiu
 LeotyLiu
发布于 2014/05/19 15:05
字数 201
阅读 16
收藏 0
//节点结构
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

vector<int> postorderTraversal(TreeNode *root) {
	//用于存放后序遍历每个节点的值
	vector<int> v;
	//用于存放遍历的节点
	stack<TreeNode *> s;
	TreeNode *cur = 0, *pre = 0;
	//根节点入栈
	s.push(root);
	while((!s.empty()) && (cur = s.top()))
	{
		//两种情况访问该节点
		//1.左右孩子不存在
		//2.访问过该节点的左孩子或者右孩子(不加这个条件就会重复访问该节点的左孩子)
		if((!cur->left && !cur->right)
		 ||(pre && (pre == cur->left || pre == cur->right)))
		{
			v.push_back(cur->val);
			pre = cur;
			s.pop();
		}
		else
		{
			//先将右孩子入栈,达到先访问左孩子的目的
			if(cur->right)
			{
				s.push(cur->right);
			}
			//再将左孩子入栈
			if(cur->left)
			{
				s.push(cur->left);
			}
		}
	}
	return v;
}


© 著作权归作者所有

LeotyLiu
粉丝 0
博文 6
码字总数 3040
作品 0
朝阳
程序员
私信 提问
二叉树的递归,非递归遍历,深度优先遍历,广度优先遍历

结果: 二叉树的递归先序遍历 A B D E H I C F J G P 二叉树的非递归先序遍历 A B D E H I C F J G P 二叉树的递归中序遍历 D B H E I A F J C P G 二叉树的非递归中序遍历 D B H E I A F J ...

tsmyk0715
2016/07/04
352
0
二叉树的遍历,深度优先遍历和广度优先遍历

原文:http://www.cnblogs.com/joyang/p/4860441.html 二叉树的遍历: D:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。 给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一...

not_in_mountain
2017/09/29
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
二叉树递归和非递归遍历

二叉树的非递归遍历 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就 是递归定义,因...

种地瓜
2016/08/03
46
0
PHP实现二叉树的深度优先遍历(前序、中序、后序)和广度优先遍历(层次)

http://blog.csdn.net/baidu_30000217/article/details/52953127 前言: 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深...

陈小龙哈
2018/06/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

64.监控平台介绍 安装zabbix 忘记admin密码

19.1 Linux监控平台介绍 19.2 zabbix监控介绍 19.3/19.4/19.6 安装zabbix 19.5 忘记Admin密码如何做 19.1 Linux监控平台介绍: 常见开源监控软件 ~1.cacti、nagios、zabbix、smokeping、ope...

oschina130111
今天
10
0
当餐饮遇上大数据,嗯真香!

之前去开了一场会,主题是「餐饮领袖新零售峰会」。认真听完了餐饮前辈和新秀们的分享,觉得获益匪浅,把脑子里的核心纪要整理了一下,今天和大家做一个简单的分享,欢迎感兴趣的小伙伴一起交...

数澜科技
今天
7
0
DNS-over-HTTPS 的下一代是 DNS ON BLOCKCHAIN

本文作者:PETER LAI ,是 Diode 的区块链工程师。在进入软件开发领域之前,他主要是在做工商管理相关工作。Peter Lai 也是一位活跃的开源贡献者。目前,他正在与 Diode 团队一起开发基于区块...

红薯
今天
8
0
CC攻击带来的危害我们该如何防御?

随着网络的发展带给我们很多的便利,但是同时也带给我们一些网站安全问题,网络攻击就是常见的网站安全问题。其中作为站长最常见的就是CC攻击,CC攻击是网络攻击方式的一种,是一种比较常见的...

云漫网络Ruan
今天
11
0
实验分析性专业硕士提纲撰写要点

为什么您需要研究论文的提纲? 首先当您进行研究时,您需要聚集许多信息和想法,研究论文提纲可以较好地组织你的想法, 了解您研究资料的流畅度和程度。确保你写作时不会错过任何重要资料以此...

论文辅导员
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部