之前在Binary Tree Preorder Traversal中说过，preorder和inorder的方法不适于Postorder因为不方便模拟第三次对节点的访问，所以只好改变方法。
首先把代码贴出来，然后详细讲解：
首先把root push近stack里，之后只要stack不为空就进入循环。首先定义pre来表示我们之前访问的节点，这个作用是用来判断我们应不应该pop出当前节点。当前节点为stack.peek()获得的节点，如果这个节点之前没有访问过，我们依次push 右子节点和左子节点，这样做是保证左子结点在栈顶(24 - 29行)。如果是叶节点或者是第二次访问的话，就pop()出来，并且加入结果集，pre设置为当前节点((20 - 23行))。
可以看到我们这样模拟省略了第二次访问节点的情况，第二次的情况是由在栈里左右子节点的相对顺序来模拟的，因为先push右子节点然后左子结点，那么首先会遍历左子树然后才遍历右子树。如果没有左子树或者右子树情况，那么就先遍历另外一个有的子树。这样由于子节点在栈里都在parent的上方，所以一定先访问完子节点再会去访问父节点，保证了算法的正确性。
Follow up: constant space 后序遍历
No comments:
Post a Comment