检查二叉树中的对称性

Question

我正在尝试检查给定树中的对称性，我的想法是我可以从具有前序遍历（NLR）的左子树和具有反向前序遍历（NRL）的右子树中创建两个数组列表，然后将两者与相等运算符进行比较，我将得到一个布尔值。我已经检查了返回的 Arraylist 值，但无论 Arraylists 中的任何匹配值，它似乎总是返回 false。任何关于为什么会发生这种情况的提示都将受到赞赏。

    import java.util.ArrayList;
    
    class BinaryTree<E>{
        public E data;
        public BinaryTree<E> left;
        public BinaryTree<E> right;
    
        public BinaryTree() {}
        public BinaryTree(E data) { this.data = data; }
        public BinaryTree(E data, BinaryTree<E> left, BinaryTree<E> right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
    
    class Solution{
        public static boolean symmetricTree(BinaryTree<Integer> root){
            System.out.println(traversal(root.left, true));
            System.out.println(traversal(root.right, false));
            return traversal(root.left, true) == traversal(root.right, false);
        }
    
        public static ArrayList<Integer> traversal(BinaryTree<Integer> root, boolean left){
            // 関数を完成させてください
            ArrayList<Integer> dArr = new ArrayList<>();
            if(left) dArr = preorderTraversalHelper(root, dArr);
            else dArr = reversePreorderTraversalHelper(root, dArr);
            //System.out.println(dArr);
            return dArr;
        }
        public static ArrayList<Integer> preorderTraversalHelper(BinaryTree<Integer> root, ArrayList<Integer> dArr){
            if (root == null) return null;
            dArr.add(root.data);
            preorderTraversalHelper(root.left, dArr);
            preorderTraversalHelper(root.right, dArr);
            return dArr;
        }
        public static ArrayList<Integer> reversePreorderTraversalHelper(BinaryTree<Integer> root, ArrayList<Integer> dArr){
            if (root == null) return null;
            dArr.add(root.data);
            reversePreorderTraversalHelper(root.right, dArr);
            reversePreorderTraversalHelper(root.left, dArr);
            return dArr;
        }
    }

Answer 1

return traversal(root.left, true) == traversal(root.right, false);

这对我来说听起来不对，在 Java 中有一个 equals 方法实际检查数组是否相等（具有相同顺序的相同元素）。您介绍的方式比较了参考文献：

var arr1 = List.of(1,2,3);
var arr2 = List.of(1,2,3);
arr1 == arr2 // this is false because the actual references are different
arr1.equals(arr2) // this yields "true"

Answer 2

你的对抗产生 false 的原因是因为你用 == 运算符对抗两个引用类型。引用包含它指向的对象的地址，而 == 运算符面对两个变量的内容。由于您面临两个引用，您正在做的是检查第一个引用包含的地址是否等于第二个引用包含的地址，因为它们都指向内存中的不同对象，因此指向不同的内存地址,本次交锋只能return假

如果要检查这两个引用是否表示相同的内容，则需要使用equals方法。但是，Collection 的 equals 方法只是在其元素上调用相同的 equals 方法，因此由于您为 BinaryTree [=26= 使用泛型类型]，您需要警告 class 的用户所提供的参数类型应该有一个正确的 equals 实现。

回到您的 traversal 方法，它应该如下所示：

public static boolean symmetricTree(BinaryTree<Integer> root){
    System.out.println(traversal(root.left, true));
    System.out.println(traversal(root.right, false));

    //Use equals to confront reference type, the == operator is only for primitive types
    return traversal(root.left, true).equals(traversal(root.right, false));
}

检查二叉树中的对称性

Check symmetry in binary tree

java

computer-science