0

我写了这个函数来检查是否n2是n1. 我使用递归，但是当我使用两棵树对其进行测试时，它向我显示了错误的答案（预期的true，但实际上返回了false）。

我挣扎了一会儿，还是说不出哪里不对劲。

private Boolean isSubTree(node n1, node n2){
    if(n1 == null)
        return false;
    if(n2 == null)
        return true;
    if(n1.data == n2.data){
        return isSubTree(n1.left,n2.left) && isSubTree(n2.right,n2.right);
    }
    else
        return isSubTree(n1.left, n2) || isSubTree(n1.right, n2);
}
4

4 回答 4

0

您的边缘情况不正确。特别是，当两者都为空时n1，n2则视为匹配子树，但如果只有一个为空，则视为不匹配。

于 2013-01-12T23:28:28.233 回答
0

我认为检查 n2 的父级以查看它是否为 n1 更容易。如果没有，一直继续，直到找到为止；在这种情况下，您返回 true。另一种情况是直到并包括根的所有父母都不是n1；在这种情况下，您返回 false。换句话说，向上工作而不是检查 n1 的所有可能的孩子及其孩子等以达到 n2。

于 2013-01-12T23:57:55.090 回答
0

有两种情况需要考虑。

  1. 如果子树必须是原始树的节点之一，那么您可以扫描树以查找匹配的子树节点。
  2. 如果子树只需要具有相等的值，那么您需要编写一个递归树相等函数并将其应用于第二个递归函数中原始树的所有叶子。
于 2013-01-12T23:59:26.937 回答
0

我同意 nabau ...如果我们在节点中有父节点的数据，最好检查天气 n2 和 n1 的根节点是否相同

否则我们可以用 n1 中每个节点的节点检查 n2 的根

在java中，我们可以比较两个对象是否相同，因为
n1中的每个节点都等于n2的根， 如果任何一个节点相等，它们是相同的

于 2013-01-13T18:14:25.513 回答