二叉树后序遍历的非递归实现 作者是 在线疯狂 发布于 2015年1月19日 在 数据结构.

二叉树的后序遍历很容易采用递归方式实现：

``````void postOrderTraversal(BinaryTree *p) {
if (!p) return;
postOrderTraversal(p->left);
postOrderTraversal(p->right);
cout << p->data;
}
``````

```树的删除。为了释放树结构的内存，某节点在被释放以前，其左右子树的节点首先应当被释放掉。

``````iterativePostorder(node)
parentStack = empty stack
lastnodevisited = null
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
parentStack.push(node)
node = node.left
else
peeknode = parentStack.peek()
if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right)
/* if right child exists AND traversing node from left child, move right */
node = peeknode.right
else
visit(peeknode)
lastnodevisited = parentStack.pop()
``````

提示：

Post-order traversal sequence: A, C, E, D, B, H, I, G, F

解决方案：

``````void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr= s.top();
// we are traversing down the tree
if (!prev || prev->left == curr|| prev->right == curr) {
if (curr->left) {
s.push(curr->left);
} else if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the left
else if (curr->left == prev) {
if (curr->right) {
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
}
// we are traversing up the tree from the right
else if (curr->right == prev) {
cout << curr->data << " ";
s.pop();
}
prev = curr;  // record previously traversed node
}
}
``````

``````void postOrderTraversalIterative(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
s.push(root);
BinaryTree *prev = NULL;
while (!s.empty()) {
BinaryTree *curr= s.top();
if (!prev || prev->left == curr|| prev->right == curr) {
if (curr->left)
s.push(curr->left);
else if (curr->right)
s.push(curr->right);
} else if (curr->left == prev) {
if (curr->right)
s.push(curr->right);
} else {
cout << curr->data << " ";
s.pop();
}
prev = curr;
}
}
``````

另一种解法：

```将根节点压入第一个栈

``````void postOrderTraversalIterativeTwoStacks(BinaryTree *root) {
if (!root) return;
stack<BinaryTree*> s;
stack<BinaryTree*> output;
s.push(root);
while (!s.empty()) {
BinaryTree *curr= s.top();
output.push(curr);
s.pop();
if (curr->left)
s.push(curr->left);
if (curr->right)
s.push(curr->right);
}
while (!output.empty()) {
cout << output.top()->data << " ";
output.pop();
}
}
``````

复杂度分析：

Pingbacks已关闭。

1. 豆花鱼 发布于 2016年1月8日 03:49 #

只有当cur是叶子节点或者当previous node是其子结点的时候才处理当前结点，其他情况直接先将cur->right push进来然后再push cur->left就可以了。代码比较简单一些，http://www.hihuyue.com/hihuyue/codepractise/leetcode/leetcode119-binary-tree-postorder-traversal

2. 赤小侸 发布于 2016年2月19日 05:02 #

最后一种方法应先把右子树push到s里?

3. 在线疯狂 发布于 2016年2月19日 18:11 #

用一棵最简单的二叉树AB##C##测试下：
A
/ \
B C

4. tst 发布于 2020年6月5日 10:54 #

双栈没有什么神奇之处，就是 把 根，右，左 的前序变种进行输出，然后逆序