菜鸟提问：用JavaScript以迭代的方式实现二叉树后序遍历有哪几种思路

Hokori

如题
现在看到的几种思路：

队列（也可以用两个栈模拟队列，个人感觉意义好像不大）

var postorderTraversal = function(root) {
    let nodestack = [];
    let res = [];
    if(root===null){
        return [];
    }
    nodestack.push(root);
    while(nodestack.length>0){
        let node = nodestack.pop();
        res.unshift(node.val);
        if(node.left){
            nodestack.push(node.left);
        }
        if(node.right){
            nodestack.push(node.right);
        }
    }
    return res;

每个结点需要进栈出栈两次，并用flag标志（摘的书上，所以是C语言，如果可以的话希望有人转成JS，因为我C太差了。。。）

typedef struct stackelemtype
{
    bitree link;
    int flag;
} stackelemtype;
void nrpostorder(bitree bt)
{
    stackelemtype stack[MAXSIZE];
    bitree p;
    int top = 0, sign;
    p = bt;
    do{
        while (p != NULL){
            stack[++top].link = p;
            stack[top].flag = 0;
            p = p->1child;
        }
        if (top > 0){
            sign = stack[top].flag;
            p = stack[top--].link;
            if (sign == 0){
                stack[++top].link = p;
                stack[top].flag = 1;
                p = p->rchild;
            }else{
                print("%d\t", p->data);
                p = NULL;
            }
        }
    }while (top > 0);
}

补充一下：书上对第二种后序遍历方式的说明

Hokori

主要是感觉第一种unshift效率不高（队列的缺点），但也是最好懂的一种
第二种出栈入栈两次感觉也很耗性能

不知道有没有更好的方法或思路

hsxfjames

Hokori 不想 unshift 可以逆序再 reverse 一下

Hokori

hsxfjames 那样的话nodestack好像就得shift了，好像避免不了对头元素的操作 😢 ，个人觉得对头元素操作的方法消耗都很大

hsxfjames

Hokori

        res.push(node.val);
        ...
    return res.reverse();

Hokori

hsxfjames 啊啊啊感谢，是我想错了！

hsxfjames

随手测了下性能（楼主发的第二种方法好长，不想看，逃）
https://jsperf.com/0xffff-post-order-btree/1

这个 unshift 真慢，瞎写的生成器都比它快。