java - 用于查找树是否对称的代码中的错误
问题描述
我编写了一个代码来检查一棵树是否对称(如果树是它自己的镜像,则它是对称的)。假设给定一棵树 A。在这里,我尝试使用函数 mirror() 创建一棵新树 B,它是树 A 的镜像。当我在 main 函数中打印树 B 时,它是正确的打印镜像。但是,当在函数 isSymmetric() 中调用相同的镜像函数时,它会返回原始树本身。其他解决方案已经在不同的平台上可用。我只想知道为什么我的代码在不同的地方调用相同的函数时表现不同。
导入 java.util.*;
类 BinaryTree { 节点根;
BinaryTree(int d) {
root = new Node(d);
}
BinaryTree() {
root = null;
}
static class Node {//why static is needed ?
int data;
Node left, right;
Node(int d) {
data = d;
left = null;
right = null;
}
}
boolean isSymmetric(Node root) {
if(root == null)
return true;
if(root.left == null && root.right == null)
return true;
Node root2 = mirror(root);
printTree(root);
System.out.println();
printTree(root2);//this should print mirror image of tree but it is printing the original tree
return isMirror(root, root2);
}
Node mirror(Node root) {
if(root == null)
return root;
if(root.left == null && root.right == null) {
return root;
}
Node left = mirror(root.left);
Node right = mirror(root.right);
root.left = right;
root.right = left;
return root;
}
boolean isMirror(Node n1, Node n2) {
if(n1 == null && n2 == null)
return true;
if(n1 == null || n2 == null)
return false;
if(n1.data != n2.data)
return false;
return isMirror(n1.left, n2.left) && isMirror(n1.right, n2.right);
}
void printTree(Node root) {
Queue<Node> q = new LinkedList<Node>();
if(root != null) {
q.add(root);
}
else {
System.out.println("empty tree");
}
while(!q.isEmpty()) {
Node y = q.remove();
System.out.print(y.data + " ");
if(y.left != null)
q.add(y.left);
if(y.right != null)
q.add(y.right);
}
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
BinaryTree t = new BinaryTree(5);
t.root.left = new Node(6);
t.root.right = new Node(4);
t.root.left.left = new Node(7);
t.root.left.right = new Node(8);
t.root.right.left = new Node(9);
t.root.right.right = new Node(10);
t.printTree(t.root);
t.root = t.mirror(t.root);
System.out.println();
t.printTree(t.root);
System.out.println();
System.out.print(t.isSymmetric(t.root));
}
}
解决方案
主要原因是您在同一个根目录上调用了两次镜像方法。第二次调用反转了第一次调用的效果。
您可以更改代码以实现这样的结果,我修复了您的 isMirror 函数中的错误。
public class BinaryTree {
Node root;
BinaryTree(int d) {
root = new Node(d);
}
BinaryTree() {
root = null;
}
public static void main(String[] args) throws java.lang.Exception {
// your code goes here
BinaryTree t = new BinaryTree(5);
t.root.left = new Node(6);
t.root.right = new Node(4);
t.root.left.left = new Node(7);
t.root.left.right = new Node(8);
t.root.right.left = new Node(9);
t.root.right.right = new Node(10);
t.printTree(t.root);
Node MirroredNode = t.mirror(t.root.clone());
System.out.println();
t.printTree(t.root);
t.printTree(MirroredNode);
System.out.println();
System.out.print(t.isSymmetric(t.root));
}
boolean isSymmetric(Node root) {
if (root == null)
return true;
if (root.left == null && root.right == null)
return true;
Node root2 = mirror(root.clone());
printTree(root);
System.out.println();
printTree(root2);//this should print mirror image of tree but it is printing the original tree
return isMirror(root, root2);
}
Node mirror(Node root) {
if (root == null)
return root;
if (root.left == null && root.right == null) {
return root;
}
Node left = mirror(root.left.clone());
Node right = mirror(root.right.clone());
root.left = right;
root.right = left;
return root;
}
boolean isMirror(Node n1, Node n2) {
if (n1 == null && n2 == null)
return true;
if (n1 == null || n2 == null)
return false;
if (n1.data != n2.data)
return false;
return isMirror(n1.left, n2.right) && isMirror(n1.right, n2.left);
}
void printTree(Node root) {
Queue<Node> q = new LinkedList<Node>();
if (root != null) {
q.add(root);
} else {
System.out.println("empty tree");
}
while (!q.isEmpty()) {
Node y = q.remove();
System.out.print(y.data + " ");
if (y.left != null)
q.add(y.left);
if (y.right != null)
q.add(y.right);
}
}
static class Node implements Cloneable {//why static is needed ?
int data;
Node left, right;
Node(int d) {
data = d;
left = null;
right = null;
}
@Override
public Node clone() {
try {
return (Node) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return null;
}
}
}
推荐阅读
- visual-studio-code - 如何使用 bazel 将所有依赖项下载到本地?
- python - Scrapy 重复过滤器可以在 Jobs 中保持不变吗?
- powerapps - 使用 Navigate on screen OnVisible 重定向未经授权的用户
- java - 如何在 Spring Boot 应用程序中测试 Quartz 作业的正常工作
- sql-server - 关于条件的 PARTITION BY 语句
- ios - 使用 Firebase 登录 iOS 13.2 的导航/Segue
- python - 如何从纽约时报网络抓取某个类别的所有文章
- c++ - 模板类使用参数包时如何传递其他模板参数?
- assembly - 当我试图在给定的汇编代码下编译时,它给出了错误未定义的符号:AXSAVE
- machine-learning - 使用用户输入测试预测模型