給定兩棵樹，你如何找到其中一棵樹是其他的子樹？

Question

給定兩棵樹，你如何找到其中一棵樹是其他的子樹？ 給這個最好的算法...並且還給出你所回答的順序...

Answer 1

首先想到的是遍歷一棵樹，看看它的任何一個孩子是否是頭另一棵樹。然後反轉。

如果你知道每棵樹的高度，你或許可以找出哪棵樹可能是另一棵樹的子樹。

如果您知道樹木的其他細節或特性（排序與否，是否平衡），您可以使用這些特性提出更快的算法。

Answer 2

以下是我們可以做的事情：假設我們有一個叫isSubSet的函數獲取兩棵樹的根。另一方面，我們有一個叫isIdentical的函數，它檢查兩棵樹是否相同。

我們假設我們想要看看樹S是否是樹T的一個子集。如果T和S是相同的，那麼它們是，否則我們通過再次調用isSubset函數來通過S。但是這次我們發送T-> Left和S作爲T的左子樹並且T->右和S作爲右子樹S.

可以在here中找到代碼和更多信息。

Answer 3

假設你有雙向樹，你應該簡單地調用這個方法兩次，複雜度將是O（k），其中k = n + m，其中n和m - 兩棵樹的高度。

isSubtree(Node n1, Node n2){ 
    while(n2.parent != null){ 
     if(n2.parent == n1){ 
     return true; 
     } 
     n2=n2.parent; 
    } 
    return false; 
} 

你可以做得更好，如果你還記得訪問父節點：

isParent(Node n1, Node n2){ 
    Set<Node> parents = new HashSet<Node>(); 
    parents.add(n1); 
    parents.add(n2); 
    while(n1.parent != null || n1.parent != null){ 
     if (parents.contains(n1.parent)){ 
      n1 is subtree of n2 
     } 
     if (parents.contains(n2.parent)){ 
      n2 is subtree of n1 
     } 
     parents.add(n1.parent); 
     parents.add(n2.parent); 
     n1=n1.parent; 
     n2=n2.parent; 
    } 
    not a subtrees 
}