给定一个二叉搜索树，其中任意两个节点被交换。所以我们需要找到那两个节点并将它们交换回来(我们需要交换节点，而不是数据)
我试图通过制作一个额外的数组来做到这一点，该数组具有树的中序遍历并且还保存指向每个节点的指针。 然后我们就遍历数组，找到排序顺序不对的两个节点，现在这两个节点在树中查找然后交换
所以我的问题是如何在 O(1) 空间内解决这个问题？
最佳答案
In order traversal在 BST 上，您可以遍历有序的元素。
你可以使用中序遍历，找到两个不在位置的元素(将它们存储在两个指针中)并将它们交换回来。
此方法实际上是动态创建您描述的数组，而不是实际创建它。
但是请注意，空间消耗不是O(1)，而是O(h)，其中h 是树，由于堆栈跟踪。如果树是平衡的，它将是 O(logn)
关于algorithm - 在 BST 中，两个节点随机交换，我们需要找到这两个节点并将它们交换回来，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11824946/