这不是家庭作业，这是一个面试问题。
这里的问题是，算法应该是常量空间。我对如何在没有堆栈的情况下做到这一点一无所知，我会用堆栈发布我写的东西，但无论如何它都不相关。
以下是我尝试过的方法：我试图进行预购遍历，我到达了最左边的节点，但我被困在那里。我不知道如何在没有堆栈/父指针的情况下“递归”备份。
任何帮助将不胜感激。
（我把它标记为Java，因为这是我很乐意使用的，但它显然与语言无关。
我没有完全考虑过，但我认为只要你愿意在这个过程中搞砸你的树，这是可能的。
每个节点都有 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;
}
}
}
