O(n)时间非递归过程遍历二叉树

Question

我正在读一本名为" 算法简介 "的书.我想很多人都知道.我刚刚碰到一个看似相当困难的问题:

编写一个O(n)-time非递归过程,给定一个n节点二叉树,打印出每个节点的密钥.在树本身之外使用不超过恒定的额外空间,并且在过程中不要修改树,即使是暂时的.

我看到还有另外一个问题:如何在没有额外内存的情况下在O(n)时间遍历二叉树,但主要区别在于我无法修改树.我正在考虑使用一些访问过的标志,但我还没有提出正确的解决方案.这可能是我看不到的明显的东西.你会如何设计一个解决这个问题的算法？即使是对答案的一些指示也会受到赞赏.

Answer 1

如果树在两个方向上链接,您可以这样做:

assert root.parent is null

now, old = root, null
while now != null:
    print now.label
    if leaf(now):
        now, old = now.parent, now
    else:
        if old == now.right:
            now, old = now.parent, now
        if old == now.left:
            now, old = now.right, now            
        if old == now.parent:
            now, old = now.left, now

这按照左,右,右的顺序打印,但您可以获得任何您喜欢的订单.

如果树只在一个方向上链接,我认为你不能这样做.你可以看看砍伐森林.