这两个查找二叉树是否等效的递归实现？

Question

问题陈述很清楚：“给定 2 个二叉树，t1 和 t2，其中 t1 >> t2，查找 t2 是否是 [=13= 的子树].

给出一个很简单的Node class:

class Node {
    String val;
    Node left;
    Node right;
    // getters, setters for 
}

我提出了 2 种不同的实现方式，它们似乎都有效。

实施 1

boolean isSubtree(Node t1, Node t2) {
    if (t1 == null || t2 == null)
        return false;

    boolean isLeftSubtree = false;
    boolean isRightSubtree = false;
    if (t1.getVal().equals(t2.getVal())) {
        isLeftSubtree = ((t1.left() == null) && (t2.left() == null)) || isSubtree(t1.left(), t2.left());
        isRightSubtree = ((t1.right() == null) && (t2.right() == null)) || isSubtree(t1.right(), t2.right());
    }

    if (isLeftSubtree && isRightSubtree)
        return true;

    return isSubtree(t1.left(), t2) || isSubtree(t1.right(), t2);
}

实施 2

boolean isSubtree(Node t1, Node t2) {
    if (t1 == null || t2 == null)
        return false;

    boolean isLeftSubtree;
    boolean isRightSubtree;
    if (t1.getVal().equals(t2.getVal())) {
        isLeftSubtree = ((t1.left() == null) && (t2.left() == null)) || isSubtree(t1.left(), t2.left());
        isRightSubtree = ((t1.right() == null) && (t2.right() == null)) || isSubtree(t1.right(), t2.right());
        return isLeftSubtree && isRightSubtree;
    }

    return isSubtree(t1.left(), t2) || isSubtree(t1.right(), t2);
}

我觉得第二个实现不正确，但我无法通过我提出的测试用例使其失败。

我的问题是，这两种实现是否相同并且都正确？（或者他们都错了，那会很尴尬..）

Answer 1

您的 2^nd 实施不正确。我们不能立即 return 写在

中的答案

return isLeftSubtree && isRightSubtree;

考虑这种情况，其中 tree1 如下：

和tree2如下：

您的代码将检查根节点本身是否相等，并得出 return 一个 false 的结论，而不给子树处理它的机会。

此外，递归方法是检查子树是否存在的好方法，但最坏情况下的时间复杂度为 O(n^2)。您可以改为序列化两棵树并检查树 2 的序列化是否存在于树 1 的序列化中。

这两个查找二叉树是否等效的递归实现？

Are these 2 recursive implementations of finding if a Binary Tree are equivalent?

java

algorithm

binary-tree