[数据结构与算法]第十题 剑指 Offer 28. 对称的二叉树

剑指 Offer 28. 对称的二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

限制

0 <= 节点个数 <= 1000

思路

注意：对称是在不同的节点，左右子树对称，例如
针对[1,2,2,3,4,4,3] 树中第二层，左节点2 与 右节点2，左节点的左子树 与 右节点的右子树构成对称，左节点的右子树与右节点的左子树构成对称
刚开始理解有误，直接判断到同一节点的左右子树
left.val === right.val

BFS

针对不同的节点，那么定义两个队列，用于存储左节点2 与 右节点2的子节点

let leftQueue = [root.left];
let rightQueue = [root.right];

• 对称说明左右节点2的子树长度是相等的
• 在左右队列不为空的情况下 分别对 leftQueue 和 rightQueue逐一做出队（出队元素定义为：L,R）操作， 出队元素出现三种情况
• L !==null && R !==null ：判断元素值是否相等 不相等则不对称，直接退出 反之将元素的子节点分别push到leftQueue 与 rightQueue 更新队列进一步搜索
• L === null && R ===null：节点不存在 退出循环
• 其他情况：
• L =null && R !null 或 L ! null && R=null 这些都是不对称的情况 直接返回 false
• 直至 循环结束leftQueue 与 rightQueue 出队完毕 则说明二叉树是 对称的

代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    // 记住要判空 []为对称二叉树
    if(!root) return true;
    //左队列
    let leftQueue = [root.left];
    //右队列
    let rightQueue = [root.right];
    //搜索
    while(leftQueue.length && rightQueue.length){
        //左队列出队
        let L = leftQueue.shift();
        //右队列出队
        let R = rightQueue.shift();
        if(L && R){
            if(L.val !== R.val){
                return false;
            }
            //当前左 右节点的子节点入队
            //当前左的 左子节点 对应 当前右的 右子节点
            //当前左的 右子节点 对应 当前右的 左子节点
            //顺序不能搞错 不然搜索判断时就会出错 
            leftQueue.push(L.left, L.right);
            rightQueue.push(R.right, R.left);
        }else if(!L && !R){
            continue;
        }else{
            return false;
        }
    }
    // 出队完毕 都没有出现 return flase 的情况 为对称
    if(leftQueue.length == 0 && rightQueue.length == 0) return true;
    else return false;
    

};