实现二叉树的后序遍历
#include \"head.cpp\"
struct Node {
Node* left;
Node* right;
int val;
Node(int v...
实现二叉树的后序遍历
#include \"head.cpp\"
struct Node {
Node* left;
Node* right;
int val;
Node(int v,Node* l,Node* r):val(v),left(l),right(r){}
};
void posOrder(Node* head) {
if(!head) return;
stack<Node*> s1;
stack<int> s2;
s1.push(head);
while(!s1.empty()) {
head = s1.top();
s1.pop();
s2.push(head->val);
if(head->left)
s1.push(head->left);
if(head->right)
s1.push(head->right);
}
while(!s2.empty()) {
int val = s2.top();
s2.pop();
cout << val << endl;
}
}
int main() {
Node head(1,nullptr,nullptr);
Node l(2,nullptr,nullptr);
Node r(3,nullptr,nullptr);
head.left = &l;
head.right = &r;
posOrder(&head);
return 0;
}
思路：
使用两个栈实现后序遍历：
后序遍历的顺序是先左再右在中，换句话说就是按照统一的二叉树遍历的方式第三次遍历到该节点的时候，访问该节点，如果是递归实现非常的简单，因为递归栈可以让我们三次访问同一个结点，可以很简单的控制。
但是使用栈的话只能两次访问同一个结点，也就是将结点放入栈的时候是第一次，从栈中弹出该节点的时候是第二次。怎样才能构造出第三次呢？其实实现的方法有很多但是有一个很简单的方式，使用2个栈。第一个栈构造中右左的访问顺序其实就是先续3遍历的变形，然后在实际处理结点的地方将处理信息放入第二个栈当中。
栈可以逆序的输出我们放入顺序的数据，所以自然就的到左右中的顺序就的到后序遍历。
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：谓词逻辑之 语法规则 下一篇：谓词逻辑之 量词等价
