【leetcode】101. 对称二叉树(Java)

题目链接101. 对称二叉树

递归迭代都要会。
递归：

• 看根节点的左右子树是否对称，与根节点无关。
• 递归终止条件：left == null && right == null
• 处理逻辑： 注意我们要做的不是验证二叉树的左右子树是否相等！ 而是是否镜像对称！所以我们递归的参数应该是check(left.left, right.right) && check(left.right, right.left)

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }

    public boolean check(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if (left.val != right.val) return false;
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

迭代：

• 我们递归方法比较的是：左子树的左节点 == 右子树的右节点 && 左子树的右节点 == 右子树的左节点
• 那我们在迭代方法中继续这么比较就好了。
• 创建一个队列，把根节点的左边节点入队，右边节点入队。然后(left.left, right.rigt）入队，（left.right, right.left）入队。两个两个取出来比较

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }

    public boolean check(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        Queue queue = new linkedList<>();
        queue.add(left);
        queue.add(right);
        while (!queue.isEmpty()){
            TreeNode q = queue.poll();
            TreeNode p = queue.poll();
            if (q == null && p == null) continue;
            if (q == null || p == null) return false;
            if (q.val != p.val) return false;
            queue.add(q.left);
            queue.add(p.right);

            queue.add(q.right);
            queue.add(p.left);
        }
        return true;
    }
}