使用恒定空间和O（n）运行时间编写二叉搜索树的非递归遍历

Question

这不是功课，这是一个面试问题。

这里的要点是算法应该是恒定空间。我对没有堆栈的情况一无所知，我会发布我使用堆栈编写的内容，但是无论如何都没有关系。

这是我尝试的方法：我尝试进行预遍历，但到达了最左边的节点，但是我被卡在那里。我不知道如何在没有堆栈/父指针的情况下“递归”备份。

任何帮助，将不胜感激。

（我将其标记为Java，因为这是我很喜欢使用的语言，但是显然它与语言无关。）

Answer 1

我没有完全考虑，但是我认为只要您愿意在此过程中弄乱您的树，这是可能的。

每个节点都有2个指针，因此可以用来表示一个双向链接列表。假设您从Root前进到Root.Left =
Current。现在Root.Left指针已无用，因此将其分配为Current.Right并转到Current.Left。当您到达最左边的孩子时，您将获得一个链接列表，其中树挂在某些节点上。现在，对其进行迭代，对您遇到的每棵树重复该过程

编辑：仔细考虑。这是按顺序打印的html" target="_blank">算法：

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