检查两棵二叉搜索树是否相等

huangapple go评论74阅读模式
英文:

Checking if 2 Binary search trees are equal

问题

以下是翻译好的部分:

我正在创建一个二叉搜索树项目,其中一个问题是创建两棵树并检查它们是否相等。当我实现这个方法时,我一直得到“firstTree 和 secondTree 相等”的结果。以下是相关代码:

BstTest2 firstTree = new BstTest2();
firstTree.addNode(50, "Francisco Domingo Carlos Andres Sebastián d'Anconia");
firstTree.addNode(25, "John Galt");
firstTree.addNode(15, "Hugh Akston");
firstTree.addNode(30, "Ragnar Danneskjöld");
firstTree.addNode(85, "Hank Reardan"); // 实现 add 方法

BstTest2 secondTree = new BstTest2();
secondTree.addNode(50, "Francisco Domingo Carlos Andres Sebastián d'Anconia");
secondTree.addNode(25, "John Galt");
secondTree.addNode(15, "Hugh Akston");
secondTree.addNode(30, "Ragnar Danneskjöld");
secondTree.addNode(75, "Midas Mulligan");
secondTree.addNode(85, "Hank Reardan");

if(firstTree.isEqual(secondTree))
{
     System.out.println("firstTree 和 secondTree 相等");
}
else
{
     System.out.println("firstTree 和 secondTree 不相等");
}

用于比较树的 isEqual 和 check 方法如下:

public boolean isEqual(BstTest2 tree1)
{
    return check(this.rootNode, tree1.rootNode);
}
public boolean check(Node node1, Node node2)
{
    if((node1 == null) && (node2 == null))
    {
        return true;
    } 
    else if((node1 == null) || node2 != null)
    {
        return false;
    } 
    else if((node1 != null) || node2 == null)
    {
        return false;
    } 
    else
    {
        return check(node1.leftChild, node2.leftChild) && check(node1.rightChild, node2.rightChild);
    }
}

我在 isEqual() 和 check() 方法中做错了什么,以至于当树不相等时我一直得到“firstTree 和 secondTree 相等”的结果?

英文:

I'm creating a binary search tree project, and one of the questions is to create 2 trees and check if they're equal or not. When I implement the method, I keep getting
firstTree and secondTree are equal. Here's the relevant code:

BstTest2 firstTree = new BstTest2();
firstTree.addNode(50, "Francisco Domingo Carlos Andres Sebastián d'Anconia");
firstTree.addNode(25, "John Galt");
firstTree.addNode(15, "Hugh Akston");
firstTree.addNode(30, "Ragnar Danneskjöld");
firstTree.addNode(85, "Hank Reardan"); //implementing add method

BstTest2 secondTree = new BstTest2();
secondTree.addNode(50, "Francisco Domingo Carlos Andres Sebastián d'Anconia");
secondTree.addNode(25, "John Galt");
secondTree.addNode(15, "Hugh Akston");
secondTree.addNode(30, "Ragnar Danneskjöld");
secondTree.addNode(75, "Midas Mulligan");
secondTree.addNode(85, "Hank Reardan");

if(firstTree.isEqual(secondTree))
{
     System.out.println("firstTree and secondTree are equal");
}
else
{
     System.out.println("firstTree and secondTree are not equal");
}

isEqual and check methods for comparing the trees

public boolean isEqual(BstTest2 tree1)
{
    return check(this.rootNode, tree1.rootNode);
}
public boolean check(Node node1, Node node2)
{
    if((node1 == null) && (node2 == null))
    {
        return true;
    } 
    else if((node1 == null) || node2 != null)
    {
        return false;
    } 
    else if((node1 != null) || node2 == null)
    {
        return false;
    } 
    else
    {
        return check(node1.leftChild, node2.leftChild) && check(node1.rightChild, node2.rightChild);
    }
}

What did I do wrong in my isEqual() and check() methods that I keep getting " firstTree and secondTree are equal" when the trees are not equal?

答案1

得分: 1

你忘记检查 node1node2 的值是否相同。

  • 如果它们不相同,则意味着这两棵树不相同。
  • 如果它们相同,则继续检查它们的左孩子和右孩子是否相同。
public boolean check(Node node1, Node node2)
{
    if((node1 == null) && (node2 == null))
    {
        return true;
    } 

    // 如果只有一个节点为null,意味着这两棵树不相同
    // 这里的两个节点都不可能同时为null,因为我们之前检查过这个条件。
    if(node1 == null || node2 == null)
    {
        return false;
    } 

    // 检查 node1 和 node2 的值是否相同
    if(node1.val != node2.val)
    {
        return false;
    } 

    return check(node1.leftChild, node2.leftChild) && check(node1.rightChild, node2.rightChild);
}
英文:

You forget to check if the value of node1 and node2 are the same.

  • If they are not the same, it means these two trees are not same.
  • If they are the same, we keep on checking if their left and right child are the same.

public boolean check(Node node1, Node node2)
{
    if((node1 == null) && (node2 == null))
    {
        return true;
    } 

    // If only one node is null, it means these two trees are not the same
    // These two nodes here couldn't both be null because we check this condition earlier.
    if(node1 == null || node2 == null)
    {
        return false;
    } 

    // Check if the value of node1 and node2 are the same
    if(node1.val != node2.val)
    {
        return false;
    } 

    return check(node1.leftChild, node2.leftChild) && check(node1.rightChild, node2.rightChild);
}

huangapple
  • 本文由 发表于 2020年7月25日 11:28:39
  • 转载请务必保留本文链接:https://go.coder-hub.com/63084017.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定