algorithm - 给定两棵树，如何找到其中一棵树是另一棵树的子树？

Question

给定两棵树，如何找到其中一棵树是另一棵树的子树？给出最好的算法……并给出你回答的顺序……

Answer 1

想到的第一件事是遍历一棵树，看看它的孩子是否是另一棵树的头。然后反转。

如果您知道每棵树的高度，您可能可以找出哪棵树可能是另一棵树的子树。

如果您知道树的其他细节或特征（排序与否，平衡与否），您可以使用这些特征提出更快的算法。

Answer 2

下面是我们可以做的：假设我们有一个名为isSubSet获取两棵树的根的函数。另一方面，我们有一个称为isIdentical检查两棵树是否相同的函数。

假设我们要查看树 S 是否是树 T 的子集。如果 T 和 S 相同，则它们是相同的，否则我们通过isSubset再次调用函数来遍历 S。但是这次我们发送 T->Left 和 S 代表 T 的左子树和 T->Right 和 S 代表 S 的右子树。

您可以在此处找到代码和更多信息。

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
}