[数据结构与算法]对称二叉树——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<TreeNode> 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<TreeNode> 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);
    }

    /**
     * 「方法一」中我们用递归的方法实现了对称性的判断，那么如何用迭代的方法实现呢？首先我们引入一个队列，
     * 这是把递归程序改写成迭代程序的常用方法。初始化时我们把根节点入队两次。
     * 每次提取两个结点并比较它们的值（队列中每两个连续的结点应该是相等的，而且它们的子树互为镜像），
     * 然后将两个结点的左右子结点按相反的顺序插入队列中。当队列为空时，
     * 或者我们检测到树不对称（即从队列中取出两个不相等的连续结点）时，该算法结束。
     * @param u
     * @param v
     * @return
     */
    public static boolean isSymmetric(TreeNode u, TreeNode v) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        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;
    }
}

阅读世界，共赴山海

423全民读书节，邀你共读