algorithm - 在二叉搜索树中查找交换的节点

Question

交换二叉搜索树的两个节点。

输入树:

     10
    /  \
   5    8
  / \
 2   20

在上面的树中，必须交换节点 20 和 8 才能修复树。

输出树:

     10
    /  \
   5    20
  / \
 2   8

我遵循了 here 中给出的解决方案.但我觉得解决方案不正确，因为:

根据网站:

1. The swapped nodes are not adjacent in the inorder traversal of the BST.

   For example, Nodes 5 and 25 are swapped in {3 5 7 8 10 15 20 25}.
   The inorder traversal of the given tree is 3 25 7 8 10 15 20 5 If we observe carefully, during inorder traversal, we find node 7 is smaller than the previous visited node 25. Here save the context of node 25 (previous node). Again, we find that node 5 is smaller than the previous node 20. This time, we save the context of node 5 ( current node ). Finally swap the two node’s values.

所以我的观点是，如果它考虑 25 因为它大于 7 而不是它应该考虑 20 因为它也大于 5。那么这是正确的解决方案还是我遗漏了什么？

Answer 1

是的。它正在考虑 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}，我们有 (4, 3) 对和 (3, 2)。假设我们有对 (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] 被交换。在 {1, 4, 3, 2, 5} 的情况下，交换了 4 和 2。

现在回到例子3 25 7 8 10 15 20 5，其中25, 7和20 5是唯一的两对顺序错误。那么 25 和 5 就是被交换的两个元素。