二叉搜索树的两个节点被交换。
输入树：
10
/ \
5 8
/ \
2 20
在上面的树中，必须交换节点 20 和 8 才能修复树。
输出树：
10
/ \
5 20
/ \
2 8
我按照这里给出的解决方案。但我觉得解决方案不正确，因为：
根据网站：
交换的节点在 BST 的中序遍历中不相邻。
例如，节点 5 和 25 交换为
{3 5 7 8 10 15 20 25}.
给定树的中序遍历是3 25 7 8 10 15 20 5如果我们仔细观察，在中序遍历过程中，我们发现节点 7 比之前访问的节点 25 小。这里保存节点 25（上一个节点）的上下文。再次，我们发现节点 5 比之前的节点 20 小。这一次，我们保存节点 5（当前节点）的上下文。最后交换两个节点的值。
所以我的观点是，如果它正在考虑 25，因为它大于 7，那么它也应该考虑 20，因为它也大于 5。那么这是正确的解决方案还是我遗漏了什么？
是的。它正在考虑 25，因为它大于 7。但是，它不应该同时考虑 20，因为它也大于 5。相反，它应该考虑 5，因为它小于 20。
这个例子不是很好，因为 5 在原始数组中的位置是最后一个。让我们考虑一个排序数组{1, 2, 3, 4, 5}。交换 2 和 4，然后我们得到{1, 4, 3, 2, 5}。如果交换排序数组中的两个元素（不相邻），对于所有像 的对(A[i], A[i+1])，将恰好有两对顺序错误，即降序。在 的情况下{1, 4, 3, 2, 5}，我们有 pair(4, 3)和 pair (3, 2)。假设我们有 pair(A[p], A[p+1])和 pair (A[q], A[q+1])，这样A[p] > A[p+1]和A[q] > A[q+1]，我们可以声称它是A[p]和A[q+1]被交换的。在 的情况下{1, 4, 3, 2, 5}，交换的是 4 和 2。
现在回到示例3 25 7 8 10 15 20 5，其中25, 7和20 5是仅有的两个顺序错误的对。然后 25 和 5 是被交换的两个元素。
遵循@jeffreys 的符号，
如果我们有对 (A[p], A[p+1]) 和对 (A[q], A[q+1])，使得 A[p] > A[p+1] 和 A[q ] > A[q+1]，我们可以说是 A[p] 和 A[q+1] 被交换了
你知道只有一个交换，它会在排序顺序中产生 2 个差异，或者如果它们相邻则只有一个差异。假设 p < q，所以 A[p],A[p+1] 是第一个降序对，而 q 是第二个。
如果没有第二对，那么交换第一对就可以修复树，这是容易的部分。否则我们知道有两个不相邻的节点。
在 A[p] 和 A[p+1] 中，我们可以说 A[p+1] 是不合适的。由于这是第一对，我们必须将 A[p+1] 向前移动到第二对，但这意味着它仍将小于保持原位的早期 A[p]，因此我们不会创建一个排序数组。因此我们必须选择 A[p]。
A[q] 和 A[q+1] 也是如此，假设 A[q] 不合适，这意味着我们必须将它向后移动，它仍然会大于 A[q+ 1]稍后出现，再次打破排序。