使用常量空间和O(n)运行时编写二进制搜索树的非递归遍历

Question

这不是作业,这是一个面试问题.

这里的问题是算法应该是恒定的空间.我对如何在没有堆栈的情况下做到这一点非常无能为力,我会发布我使用堆栈编写的内容,但无论如何它都不相关.

这是我尝试过的:我试图进行预订遍历,然后我到了最左边的节点,但我被困在那里.我不知道如何在没有堆栈/父指针的情况下"recurse"备份.

任何帮助,将不胜感激.

(我将它标记为Java,因为这是我很习惯使用的,但它显然是语言无关的.)

Answer 1

我并没有完全认为它,但我认为只要你愿意在这个过程中弄乱你的树,这是可能的.

每个节点都有2个指针,因此它可以用来表示双向链表.假设你从Root前进到Root.Left = Current.现在Root.Left指针是无用的,所以将它指定为Current.Right并继续到Current.Left.当你到达最左边的孩子时,你会有一个链表,树上挂着一些节点.现在迭代一遍,重复你遇到的每一棵树的过程

编辑:想通了.这是按顺序打印的算法:

void traverse (Node root) {
  traverse (root.left, root);
}

void traverse (Node current, Node parent) {
  while (current != null) {
    if (parent != null) {
      parent.left = current.right;
      current.right = parent;
    }

    if (current.left != null) {
      parent = current;
      current = current.left;
    } else {
      print(current);
      current = current.right;
      parent = null;
    }
  }
}

Answer 2

Morris Inorder树遍历怎么样？它基于线程树的概念,它修改了树,但在完成后还原它.

Linkie:http://geeksforgeeks.org/？p = 6358

不使用任何额外的空间.

Answer 3

如果您使用基于向下指针的树并且没有父指针或其他内存，则不可能在常量空间中遍历。

如果您的二叉树位于数组中而不是基于指针的对象结构中，则这是可能的。但是这样你就可以直接访问任何节点。这是一种作弊;-)