一种简单的迭代法后序遍历

主要是借助两个辅助栈，一个节点栈和一个 data 栈，data 栈中存放的是每个节点 data 的逆序。
考虑后序遍历固定是根节点最后访问，如果我们逆序一下，则根节点可以最先访问，首先确定下来。
即先得到一个逆序版的后序遍历，再通过一个栈的倒腾还原。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


template <class T, class VST>
void travPost_I(BinNodePosi(T) x, VST& visit) {
    if (NULL == x) return;

    Stack<BinNodePosi(T)> S1;
    S1.push(x);
    Stack<int> S2;
    while (!S1.empty()) {
        x = S1.pop();
        if (x->lchild != NULL) S1.push(x->lchild);
        if (x->rchild != NULL) S1.push(x->rchild);
        S2.push(x->data);
    }
    while (!S2.empty())
        visit(S2.pop());
}

需要注意的是，在往节点栈中 push 孩子节点的时候，先被 push 的是左孩子，因为我们需要的是一个逆序版的后序遍历。

这种方法空间复杂度和时间复杂度都会多出一个O(n)，但对比查找最高左侧可见叶节点的方法，实现起来要简单很多。

Contents