二叉树后序遍历的简单实现

r囧r小猫 2022-04-03 12:22 130阅读 0赞

#### 实现二叉树的后序遍历 ####

#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遍历的变形，然后在实际处理结点的地方将处理信息放入第二个栈当中。  
栈可以逆序的输出我们放入顺序的数据，所以自然就的到左右中的顺序就的到后序遍历。