如果二叉树是等价的,这两个递归实现是等价的吗?

问题很清楚:“给定两棵二叉树, t1 和 t2 哪里 t1 >> t2 t2型 是 t1级 .

Node 班级:

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

我想出了两种不同的实现,它们看起来都有效。

实施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);
}

我有一种感觉,第二个实现是不正确的,但我不能使它失败的测试用例,我想出了。