用于查找树是否对称的代码错误

Question

我写了一个代码来检查一棵树是否对称（如果树是它自己的镜像，那么它就是对称的）。比方说，我们有一棵树 A。在这里，我尝试使用函数 mirror() 创建一棵新树 B，它是树 A 的镜像。当我在 main 函数中打印树 B 时，它是正确的打印镜像。但是，当在函数 isSymmetric() 中调用相同的镜像函数时，它 returns 原始树本身。其他解决方案已经在不同的平台上可用。我只想知道为什么在不同的地方调用同一个函数时我的代码会有不同的行为。

导入java.util.*;

class 二叉树 { 节点根；

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

}

Answer 1

主要原因是您在同一个根上调用了两次镜像方法。第二次调用与第一次调用的效果相反。

您可以更改您的代码以获得这样的结果，您的 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;
        }
    }
}

Answer 2

在isMirror中，两个节点相对于左子树和右子树是镜像的：

return isMirror(n1.left, n2.right) && isMirror(n1.right, n2.left);

为了良好的秩序：

static boolean isMirror(Node n1, Node n2)

创建一个 mirror(...) 我不会做。我没有看到创建节点以复制所有节点。

boolean isSymmetric(Node root) { ...
    return isMirror(root, root);

用于查找树是否对称的代码错误

Bug in code for finding if a tree is symmetric or not

java

binary-tree