檢查兩個二叉搜索樹具有相同的有序遍歷

Question

檢查兩個二叉搜索樹具有相同的有序遍歷。我的幼稚方法是按順序遍歷給定的兩棵樹並分別將每個元素複製到一個數組上，然後檢查這兩個數組是否相同。但我覺得我們應該能夠將一棵樹中的元素複製到一個數組中，並使用該數組來驗證另一棵樹，而不是使用兩個數組。或者更好的是，可能有辦法做到這一點，而不使用任何數組。我的代碼如下，不知道我的hasSameInOrder（）的實現是否正確。或者我們可以做到這一點，而不使用任何數組？ 請注意，如果在按順序遍歷時將元素複製到數組上，那麼具有相同遍歷遍歷的兩棵樹意味着兩個結果數組應具有相同的值。所以它們不一定具有相同的結構以便具有相同的順序遍歷。

public boolean checkTwoBSTHaveSameInOrder(Node n1, Node n2) { 
    LinkedList<Node> queue = new LinkedList<Node>(); 
    inOrder(n1, buffer); 
    hasSameInOrder(n2, queue) 
    return queue==null? false: true; 
} 
public void inOrder(Node node, LinkedList<Node> queue) { 
    if (node==null) 
     return; 
    inOrder(node.left, queue); 
    queue.add(node); 
    inOrder(node.right, queue); 
} 
public void hasSameInOrder(Node node, LinkedList<Node> queue) { 
    if (node==null) 
     return; 
    hasSameInOrder(n2.left, queue)); 
    if (queue==null) 
     return; 
    else { 
     if (node!=queue.poll()) 
      queue=null; 
    } 
    hasSameInOrder(n2.right, queue)); 
} 

Answer 1

使用一個循環的迭代執行序遍歷的兩個trees.You將需要兩個加棧（讀隊列）來跟蹤比賽。顯然，這不會改善最壞情況下的漸進時間，但這種方法無法做到更好，但手頭方法可以確保在隨機樹對上獲得合理的時間增益。

Answer 2

您可以使用以下方式單一陣列： -

int count =0; 
int[] arr; 

void inorder(node*p) { 

    if(p!=null) { 

     inorder(p->left); 
     arr[count++] = p->data; 
     inorder(p->right); 
    } 

} 

int c2 =0; 
boolean checkSame(node*p,int[] arr) { 

    if(p!=null) { 
     boolean t = true; 
     t = checkSame(p->left,arr); 
     if(c2+1>=count||arr[c2++]!=p->data) { 

      return(false); 
     } 
     return(t&&checkSame(p->right,arr)); 

    } 

} 

Answer 3

如果我們能夠重組的樹，然後轉移既樹木向左或向右傾斜格式，然後做一個遍歷Skewed Tree比較

否則，我們可以通過僅將一棵樹轉換爲偏斜格式並在進行其他遍歷中進行比較來避免成本。

Answer 4

是的，有一種方法可以不使用數組。我們可以使用線程來實現它。我們可以使用wait（）和notify（）在線程間進行交互。在單獨線程中的兩個樹中觸發遞歸inorder遍歷。讀取一棵樹中的第一個元素並等待其他樹讀取其第一個元素。比較這些元素並繼續處理其餘元素。您可以按照下面的示例代碼。

//common lock for both threads 
Object lock = new Object(); 

// flag to check if traverseFirstTree can come out of wait or not 
boolean proceedFirst = false; 

// flag to check if traverseSecondTree can come out of wait or not 
boolean proceedSecond = false; 

//value of current element in second BinarySearchTree 
int element; 

boolean identicalInorderOrNot(BST bst1, BST bst2){ 
    //check if no. of elements in both are same. If not return false 
    if (bst1.size() != bst2.size()){ 
    return false; 
    } 
    Thread thread = new Thread (new Runnable(){ 
    void run(){ 
     traverseSecondTree(bst2); 
    } 
    }); 
    //it does not matter if traverseSecondTree gets executed before traverseFirstTree(), as we have check for this condition 
    thread.start() 
    return traverseFirstTree(bst1); 
} 

private boolean traverseFirstTree(BST node){ 
    if(bst1 == null){ 
    return true; 
    } 
    if (!traverseFirstTree(node.left)){ 
    return false; 
    } 
    synchronized(lock){ 
    proceedFirst = false; 
    while (!proceedFirst){ 
     proceedSecond = true; 
     wait(); 
    } 
    notify() 
    } 
    //check if root data of bst1 is same as current element of bst2 
    if (node.data != element){ 
    return false; 
    } 
    return traverseFirstTree(node.right) 
} 

private void traverseSecondTree(BST node){ 
    if (node == null){ 
    return true; 
    } 
    traverseSecondTree(node.left) 
    synchronized(lock){ 
    while (!proceedSecond){ 
     wait(); 
    } 
    element = node.data; 
    proceedFirst = true; 
    proceedSecond = false; 
    notify(); 

    traverseSecondTree(node.right) 
}