java - 使用常数空间和 O(n) 运行时间编写二叉搜索树的非递归遍历

Question

这不是作业，这是一道面试题。

这里的问题是算法应该是常数空间。 我对如何在没有堆栈的情况下执行此操作一无所知，我会发布我使用堆栈编写的内容，但无论如何它都不相关。

这是我尝试过的:我尝试进行预排序遍历，然后到达了最左侧的节点，但我被困在那里。我不知道如何在没有堆栈/父指针的情况下“递归”备份。

任何帮助将不胜感激。

(我将其标记为 Java，因为这是我习惯使用的，但显然它与语言无关。)

Answer 1

我没有完全考虑清楚，但我认为这是可能的，只要你愿意在这个过程中搞砸你的树。

每个节点都有2个指针，所以它可以用来表示一个双向链表。假设您从 Root 前进到 Root.Left=Current。现在 Root.Left 指针没用了，因此将其分配为 Current.Right 并继续执行 Current.Left。当您到达最左边的 child 时，您将拥有一个链接列表，其中的树卡在一些节点上。现在迭代它，为你遇到的每棵树重复这个过程

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

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;
    }
  }
}