Learning to be Giant.

非递归的后序遍历

|

在Leetcode上面的这道题Binary Tree Postorder Traversal

没曾想这个题一遍就过了,尽管我的算法判断逻辑比较复杂。

  1. 维护两个栈,一个(nodes)的栈顶表示当前的节点,另一个(subtree)用于记录每个节点的那一棵子树已经被遍历。
  2. subtree的大小始终保持比nodes小1或者与nodes相同。比nodes小1意味着当前nodes栈顶的元素没有与之对应的子树的记录,即尚未有子树被遍历,即左子树尚未被遍历。如果subtree的大小与nodes相同表示nodes栈顶(即当前元素)的子树已经被遍历了。
    1. 如果subtree的大小与nodes相同 && subtree.top()==1表示左子树已经被遍历,应该开始遍历右子树
    2. 如果subtree的大小与nodes相同 && subtree.top()==2表示右子树已经被遍历,对该节点的遍历已经完成,可以弹出

之后我在discussion里面看到一个别的解法,感觉很好。其实这个别的解法我当时在做AI项目的时候自己写出来过,当时不是为了做后序遍历,而是为了做DFS,所以在刚刚拿到这个题的时候没有第一时间想到这个解法。

Disclaimer: This is a personal weblog. The opinions expressed here represent my own and not those of any entity with which I have been, am now, or will be affiliated.

Comments