如题 现在看到的几种思路:
队列(也可以用两个栈模拟队列,个人感觉意义好像不大)
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); }
补充一下:书上对第二种后序遍历方式的说明
主要是感觉第一种unshift效率不高(队列的缺点),但也是最好懂的一种 第二种出栈入栈两次感觉也很耗性能
不知道有没有更好的方法或思路
Hokori 不想 unshift 可以逆序再 reverse 一下
hsxfjames 那样的话nodestack好像就得shift了,好像避免不了对头元素的操作 😢 ,个人觉得对头元素操作的方法消耗都很大
Hokori
res.push(node.val); ... return res.reverse();
hsxfjames 啊啊啊感谢,是我想错了!
随手测了下性能(楼主发的第二种方法好长,不想看,逃) https://jsperf.com/0xffff-post-order-btree/1
这个 unshift 真慢,瞎写的生成器都比它快。
© 2018-2023 0xFFFF