二叉树的后序非递归遍历(双栈法)

深藏阁楼爱情的钟 2022-08-05 10:30 29阅读 0赞

**Alternative Solution:**  
An alternative solution is to use two stacks. Try to work it out on a piece of paper. I think it is quite magical and beautiful. You will think that it works magically, but in fact it is doing a reversed pre-order traversal. That is, the order of traversal is a node, then its right child followed by its left child. This yields post-order traversal in reversed order. Using a second stack, we could reverse it back to the correct order.

Here is how it works:

1.  Push the root node to the first stack.
2.  Pop a node from the first stack, and push it to the second stack.
3.  Then push its left child followed by its right child to the first stack.
4.  Repeat step **2)** and **3)** until the first stack is empty.
5.  Once done, the second stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the second stack one by one and you’re done.

void PostOreder_NoReccursive(Bitree  *T)
    {
    	stack<Bitree *>s1, s2;
    	Bitree *curr; //指向当前要检查的节点
    	s1.push(T);
    	while (!s1.empty())
    	{
    		curr = s1.top();
    		s1.pop();
    		s2.push(curr);
    		if (curr->pLeft)
    			s1.push(curr->pLeft);
    		if (curr->pRight)
    			s1.push(curr->pRight);
    	}
    	while (!s2.empty())
    	{
    		printf("%c ", s2.top()->iValue);
    		s2.pop();
    	}
    }

**Complexity Analysis:**  
The two-stack solution takes up more space compared to the first solution using one stack. In fact, the first solution has a space complexity of *O*( *h*), where *h* is the maximum height of the tree. The two-stack solution however, has a space complexity of *O*( *n*), where *n* is the total number of nodes.