在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 
}