对称二叉树——Leetcode

 代码实现:

public class IsSymmetric {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
//        [1,2,3]
//        [1,2,2,3,4,4,3];
//        [1,2,2,null,3,null,3]

        TreeNode root = new TreeNode(1);
        TreeNode l1 = new TreeNode(2);
        TreeNode l2 = new TreeNode(2);
        TreeNode l3 = new TreeNode(3);
        TreeNode l4 = new TreeNode(4);
        TreeNode l5 = new TreeNode(4);
        TreeNode l6 = new TreeNode(3);
        root.left = l1;
        root.right = l2;
        l1.left = l3;
        l1.right = l4;
        l2.left = l5;
        l2.right = l6;

        System.out.println(isSymmetric(root));

    }

    //层序遍历，慢的一批,空间也占用很多
    public boolean isSymmetric1(TreeNode root) {
        if (root.left == null && root.right == null) {
            return true;
        }
        List list = new ArrayList<>();
        list.add(root.left);
        list.add(root.right);
        while (!list.isEmpty()) {
            for (int i = 0; i < list.size() / 2; i++) {
                if (list.get(i) == null && list.get(list.size() - 1 - i) == null || (list.get(i) != null && list.get(list.size() - 1 - i) != null && list.get(i).val == list.get(list.size() - 1 - i).val)) {
                } else {
                    return false;
                }
            }
            List temp = new ArrayList<>();
            boolean allNull = true;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i) == null) {
                    temp.add(null);
                    temp.add(null);
                } else {
                    allNull = false;
                    temp.add(list.get(i).left);
                    temp.add(list.get(i).right);
                }
            }
            if (allNull) {
                break;
            }
            list = temp;
        }
        return true;
    }


    //递归 思路，转化成 比较两颗子树，
    public static boolean isSymmetric2(TreeNode root) {
        return isSymmetric2(root.left, root.right);
    }


    public static boolean isSymmetric2(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        }

        if ((left == null  || right == null)) {
            return false;
        }

        return left.val == right.val && isSymmetric2(left.left, right.right) && isSymmetric2(left.right, right.left);
    }


    public static boolean isSymmetric(TreeNode root) {
        return isSymmetric(root, root);
    }

    
    public static boolean isSymmetric(TreeNode u, TreeNode v) {
        Queue q = new LinkedList();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}