algorithm - 在 BST 中，两个节点是随机交换的，我们需要找到这两个节点并将它们交换回来

Question

给定一棵二叉搜索树，其中任意两个节点被交换。所以我们需要找到这两个节点并将它们交换回来（我们需要交换节点，而不是数据）

我试图通过制作一个额外的数组来做到这一点，该数组具有树的中序遍历并保存指向每个节点的指针。然后我们只是遍历数组，找到没有排序顺序的两个节点，现在这两个节点在树中搜索然后交换

所以我的问题是如何在 O(1) 空间中解决这个问题？

Answer 1

在 BST 上的顺序遍历为您提供了对元素的遍历，有序。
您可以使用中序遍历，找到两个不合适的元素（将它们存储在两个指针中）并将它们交换回来。

此方法实际上是在动态创建您描述的数组，而不是实际创建它。

但是请注意，由于堆栈跟踪，空间消耗不是O(1)，而是树O(h)的高度。h如果树是平衡的，它将是O(logn)

Answer 2

根据 BST，这可以在 O(1) 中完成。

例如，如果树的节点有一个指向其父节点的指针，您可以使用 Wikipedia 页面的 nonRecrusiveInOrderTraversal 部分中描述的实现Tree_traversal。

作为另一种可能性，如果 BST 存储为一维数组，而不是节点之间的指针，您可以简单地遍历数组（并进行数学运算以确定每个节点的父节点和子节点）。

在进行遍历/行走时，检查当前元素是否在正确的位置。

如果不是，那么您只需查看它应该在树中的哪个位置，并与该位置的元素进行交换。（如果根在错误的位置，请注意）。

Answer 3

我们可以修改下面的 isBST() 方法来交换这两个随机交换的节点并纠正它。

/* Returns true if the given tree is a binary search tree
 (efficient version). */
int isBST(struct node* node)
{
  struct node *x = NULL;
  return(isBSTUtil(node, INT_MIN, INT_MAX,&x));
}

/* Returns true if the given tree is a BST and its
   values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max, struct node **x)
{

  /* an empty tree is BST */
  if (node==NULL)
     return 1;

  /* false if this node violates the min/max constraint */
  if (node->data < min || node->data > max) {
     if (*x == NULL) {
        *x = node;//same the first incident where BST property is not followed.
     }
     else {
        //here we second node, so swap it with *x.
        int tmp = node->data;
        node->data = (*x)->data;
        (*x)->data = tmp;

     }
     //return 0;
     return 1;//have to return 1; as we are not checking here if tree is BST, as we know it is not BST, and we are correcting it.
  }
  /* otherwise check the subtrees recursively,
   tightening the min or max constraint */
  return
    isBSTUtil(node->left, min, node->data-1, x) &&  // Allow only distinct values
    isBSTUtil(node->right, node->data+1, max, x);  // Allow only distinct values
}