algorithm - 一棵树是另一棵树的子树吗？

Question

来自 Lakmann :查找一棵树是否是另一棵树的子树: 作者说解决方案(转载如下)是 O(log(n) + log(m)) 内存，其中 n 和 m 是每棵树各自的节点数。我不明白为什么会这样。有什么指点吗？

boolean containsTree(TreeNode t1, TreeNode t2){
    if (t2 == null){
        return true;
    }
    return subTree(t1, t2);
}

boolean subTree(TreeNode r1, TreeNode r2){
    if (r1 == null){
        return false;
    }
    if (r1.data == r2.data){
        if (matchTree(r1, r2)){
            return true;
        }
    }
    return (subTree(r1.left, r2) || subTree(r1.right, r2));
}

boolean matchTree(TreeNode r1, TreeNode r2){
    if (r2 == null && r1 == null){
        return true;
    }
    if (r1 == null || r2 == null){
        return false;
    }

    if (r1.data != r2.data){
        return false;
    }

    return (matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right)); 
}

Answer 1

请考虑这个具体的例子:

t1

            1
           /
          1
         /
        1
       /
      1
     /
    1
   /
  1

t2

    1
   / \
  1   1

现在检查 t2 是否包含在 t1 中。

毫无疑问，matchTree将在最后一步失败，t1 将遍历整棵树以发现它不包含。

因此，在退化树中，这是最坏的情况，复杂度为 O(mn)。

更新:

如果两棵树是平衡的，但没有排序，唯一可以优化的是，我们知道当 t1 的子树比 t2 短时我们可以停止，即 log(n) < log(m) ，所以复杂度可以优化为

O(2^(log(n)-log(m))*m) = O(n/m*m) = O(n)

更新2:

如果已排序且没有重复元素，则可以在O(log(n)) 中的t1 中找到t2 的根。 (如果存在)，需要进行一次树遍历，即O(m) .所以它应该总结为 O(log(n) + m) .