algorithm - O(n) 时间非递归程序遍历二叉树

Question

我正在读一本名为“算法导论”的书。我想你们很多人都知道。我刚刚遇到了一个似乎相当困难的问题:

Write an O(n)-time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.

我看到还有一个这样的问题:How to traverse a binary tree in O(n) time without extra memory但主要区别在于我无法修改树。我正在考虑使用一些已访问的标志，但我还没有提炼出正确的解决方案。这可能是我看不到的显而易见的事情。您将如何设计解决此问题的算法？即使是一些指向答案的指针，我们也将不胜感激。

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

这会以根、左、右的顺序打印，但你可以得到任何你喜欢的顺序。

如果树只在一个方向上链接，我认为你做不到。你可以看看Deforestation .