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

Question

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

我试图做一个额外的数组，它具有遍历树的序列，并且还保存指向每个节点的指针。 然后我们只是遍历数组，并找到两个节点不是按排序顺序，现在这两个节点在树中搜索，然后交换

所以我的问题是如何解决O（1）中的这个问题，空间 ？

Answer 1

In order traversal在BST上给你遍历元素的顺序。
您可以使用按顺序遍历，找到两个不适合的元素（将它们存储在两个指针中）并将它们交换回来。

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

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

Answer 2

根据BST，这可以在O（1）中完成。例如，如果树的节点有指向他们父母的指针，则可以使用维基百科页面的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 
}