一棵樹的價值與​​其他樹匹配

Question

我正在解決樹上的一些問題以爲科技採訪做準備。我偶然發現了一個問題，查看是否有例如

  3  is part of    4 
     /\ ----------->   /\ 
     7 9       3 7 
             /\ 
              8 9 

一個樹（子）另一棵樹（主樹）的匹配值

的價值觀，我想出了以下的解決方案。

public static boolean isSubset(TreeNode<String> subNode, TreeNode<String> mainNode){ 
    if(subNode == null)  
     return true; 

    if(mainNode == null) 
     return false; 

    if(subNode.data.equals(mainNode.data)){ 
     return (isSubset(subNode.left,mainNode) && isSubset(subNode.right,mainNode)); 
    }else{ 
     return (isSubset(subNode,mainNode.left) || isSubset(subNode,mainNode.right)); 
    } 
} 

但是這個解決方案只檢查節點是否與mainTree中的順序相同（根，左和右）。 我應該在上面的代碼中更改哪些內容，以便我可以檢查子樹中每個節點的主樹的每個節點的匹配情況？

Answer 1

如果我明白你的要求，你完全不關心樹結構;您只需測試植根於subNode的樹的每個元素是否存在於植根於mainNode的樹中。我建議你開發一個謂詞（我們稱之爲contains），測試一個值是否在樹中。那麼你可以建立在：

public static boolean isSubset(TreeNode<String> subNode, TreeNode<String> mainNode){ 
    if(subNode == null)  
     return true; 

    if(mainNode == null) 
     return false; 

    return mainNode.contains(subNode.data) 
     && isSubset(subNode.left, mainNode) 
     && isSubset(subNode.right, mainNode); 
}