Binary Tree Postorder Traversal(各种非递归实现，完美利用栈结构模拟)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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);
}
}