Binary Tree Postorder Traversal(各种非递归实现,完美利用栈结构模拟)
2024-09-03 16:05:37
1.后序遍历的非递归实现。(左右根)
难点:后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中,要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点,这就为流程的控制带来了难题。下面介绍两种思路。
思路:有个关键的就是unUsed这个标识符。
当unUsed=1时,表示该节点未遍历过,即以该节点为根节点的左右孩子不曾遍历。
当unUsed=0时,表示该节点的左右孩子都已经被访问过。
由于入栈的顺序和出栈的顺序相反,所以若unUsed=1,则左根右节点依次入栈,且根节点的unUsed置为0.
代码:
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> res;
if(root==NULL) return res;
stack<pair<TreeNode*,int>> s;
int unUsed;
s.push(make_pair(root,)); while (!s.empty())
{
root=s.top().first;
unUsed=s.top().second;
s.pop();
if(unUsed){
s.push(make_pair(root,));
if(root->right)
s.push(make_pair(root->right,));
if(root->left)
s.push(make_pair(root->left,));
}else{
//cout<<root->val<<" ";
res.push_back(root->val);
}
}
}
};
2.拓展,中序遍历的非递归实现(左根右)。和以上思路类似,由于也不能先访问根节点,但是我们是从根节点出发,所以还是使用unUsed来标志根节点的状态。
往栈中放节点的顺序倒过来即:左根右,且该根节点的左右孩子访问完毕。
代码:
void inOrder(Node *p)
{
if(!p)
return;
stack< pair<Node*,int> > s;
Node *t;
int unUsed;
s.push(make_pair(p,));
while(!s.empty())
{
t=s.top().first;
unUsed = s.top().second;
s.pop();
if(unUsed)
{
if(t->right)
s.push( make_pair(t->right,) );
s.push( make_pair(t,) );
if(t->left)
s.push( make_pair(t->left,));
}
else printf("%d\n",t->data);
}
}
3.前序非递归,直接先根节点。
void preOrder(Node *p) //非递归
{
if(!p) return;
stack<Node*> s;
Node *t;
s.push(p);
while(!s.empty())
{
t=s.top();
printf("%d\n",t->data);
s.pop();
if(t->right) s.push(t->right);
if(t->left) s.push(t->left);
}
}
最新文章
- .Net中的AOP系列之《间接调用——拦截方法》
- LinqToDB 源码分析——生成表达式树
- 21个高质量的Swift开源iOS App
- 《驾驭Core Data》 第三章 数据建模
- inux中tail命令---用于查看文件内容
- python之高阶函数编程
- NYIST OJ 题目38 布线问题
- Centos7安装InfluxDB1.7
- java中函数的参数传递
- Python之使用Pandas库实现MySQL数据库的读写
- RJ45连接器
- C++程序设计方法3:派生类对象的构造和析构过程
- Yarn 的日志聚集功能配置使用
- MariaDB数据库性能优化
- vivado自定IP例化的问题,怎么生成VHDL的例化
- LINE@生活圈招募好友秘笈
- 【新题】OCP 062题库出现很多新题-6
- node (1)
- bzoj 3473 后缀自动机多字符串的子串处理方法
- linux在文件中包含某个关键词的指定行插入内容