BSTでは、2つのノードがランダムにスワップされます。これらの2つのノードを見つけ出し、スワップする必要があります。

Question

2つのノードがスワップされたバイナリ検索ツリーが与えられます。したがって、これらの2つのノードを見つけ出し、それらを元に戻す必要があります（データではなく、ノードを交換する必要があります）。

これは、ツリーのinorderを横断する追加配列を作成することでこれを試みました。各ノードへのポインタ。 次に、配列をたどって、ソートされた順序にない2つのノードを見つけました。これらの2つのノードはツリー内で検索され、スワップされました。

私の質問はO（1）スペース ？

Answer 1

In order traversalをBSTに追加すると、要素の走査が行われます。
インオーダートラバーサルを使用して、2つの不在要素を見つけ（2つのポインタに格納）、それらを元に戻すことができます。

このメソッドは、実際には実際に作成することなく、オンザフライで記述した配列を実際に作成しています。

ただし、スペース消費量はO(1)ではありません。O(h)ここで、hはスタックトレースによるツリーの高さです。ツリーが均衡している場合、それはO(logn)

Answer 2

になります。これはO（1）で実行できます。

たとえば、ツリーのノードが親に戻るポインタを持っている場合は、WikipediaページのnonRecrusiveInOrderTraversalセクションで説明されている実装をTree_traversalに使用できます。

もう1つの可能性として、BSTがノード間のポインタではなく、1次元配列として格納されている場合は、配列を歩いて（各ノードの親と子を決定するために数学を実行する）ことができます。

トラバーサル/ウォークを実行中に、現在の要素が正しい場所にあるかどうかを確認します。

そうでない場合は、ツリー内のどこにあるのかを確認し、その場所の要素と入れ替えることができます。 （ルートが間違った場所にあるかどうか気をつけてください）。

Answer 3

以下のようにisBST（）メソッドを変更して、2つのランダムにスワップされたノードを交換して修正することができます。

/* 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 
}