w*****1
发帖数: 245 | 1 我的做法要walk两遍. 先做reverse pre-order walk, 存到另一个stack里, 最后再pop
出来正好就是post-order.
这个似乎不太好.
请高手出来给个正解吧, 我哪都查不到阿 | r****o
发帖数: 1950 | 2 pre-order walk和post-order walk的顺序好像没什么关系啊。
pop
【在 w*****1 的大作中提到】
: 我的做法要walk两遍. 先做reverse pre-order walk, 存到另一个stack里, 最后再pop
: 出来正好就是post-order.
: 这个似乎不太好.
: 请高手出来给个正解吧, 我哪都查不到阿
| w*****1
发帖数: 245 | 3 reverse pre-order: root, right, left
post-order: left, right, root
【在 r****o 的大作中提到】
: pre-order walk和post-order walk的顺序好像没什么关系啊。
:
: pop
| j**l
发帖数: 2911 | 4 你这方法我以前也见过，也总结出来可行
前序是N L R
逆前序是N R L
后序是L R N, 结果恰好和逆前序互为逆序
这种方法把后序化归为前序,思想挺好的
我现在还不知道有没有其他不用mark的非递归后序遍历方法。
【在 w*****1 的大作中提到】
: reverse pre-order: root, right, left
: post-order: left, right, root
| b******v
发帖数: 1493 | 5 为什么一般的递归不行？
pop
【在 w*****1 的大作中提到】
: 我的做法要walk两遍. 先做reverse pre-order walk, 存到另一个stack里, 最后再pop
: 出来正好就是post-order.
: 这个似乎不太好.
: 请高手出来给个正解吧, 我哪都查不到阿
| r****o
发帖数: 1950 | 6 哦，这个想法好。
【在 w*****1 的大作中提到】
: reverse pre-order: root, right, left
: post-order: left, right, root
| j**l
发帖数: 2911 | 7 递归是树遍历的平凡解法，面试时候肯定不会就让你用递归写。
非递归又数后序最麻烦，通常的解法都要用到mark，后序非递归遍历也是清华老严教材
的习题
【在 b******v 的大作中提到】
: 为什么一般的递归不行？
:
: pop
| w*****1
发帖数: 245 | | j**l
发帖数: 2911 | 9 我们当时任课老师提示就是用mark，还说太难，考试只考前序和中序的非递归，结果考
题是不用递归求二叉树的最大深度（可以用前序和中序非递归实现，也可以用层序的队
列实现)
网上别人给出的老严习题解答，用的也是mark
【在 w*****1 的大作中提到】
: 老严用的也是mark?
| w*****1
发帖数: 245 | |
|
