英文:
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
你忘记检查 node1
和 node2
的值是否相同。
- 如果它们不相同,则意味着这两棵树不相同。
- 如果它们相同,则继续检查它们的左孩子和右孩子是否相同。
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);
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论