对称的二叉树

题目描述

示例

代码

代码1 层次遍历的变形，一层一层的比对结果，对于只有一侧的节点，可以增加一个虚拟节点用来匹配对称性

/*
层次遍历，比对结果
使用「层序遍历」的方式进行「逐层检查」，对于空节点使用 placeHolder 进行代指，同时确保不递归 placeHolder 对应的子节点。
1. 起始时，将 root 节点入队；
2. 从队列中取出节点，检查节点是否为 placeHolder 节点来决定是否继续入队：
    2.1 当不是 placeHolder 节点时，将其左/右儿子进行入队，如果没有左/右儿子，则用 placeHolder 代替入队；
    2.2 当是 placeHolder 节点时，则忽略
3. 在进行流程  的同时使用「临时列表」记录当前层的信息，并检查当前层是否符合 “对称” 要求；
4. 循环流程 2 和 3 直到整个队列为空。
    
*/
function isSymmetrical(pRoot)
{
    if(!pRoot) return true // 空节点默认为对称节点
    
    //层次遍历，一层一层的比对
    let q  = [] // 使用数组模拟队列 先入先出
    q.push(pRoot) // 入队
    
    // 定义一个 占位节点，当某个节点只有左节点或者右节点时，比对的时候在另一侧塞一个占位节点
    let placeHolder = new TreeNode('null')
    
    // 开始层次遍历，变形，不一个一个遍历了，把每一行的数值塞到一个临时数组中，每次校验一行
    while(q.length > 0){
        
        let size = q.length
        let list = [] // 临时数组，存储本层的数值，判断是否对称
        
        while(size > 0){
            let current = q.shift() // 每次出队一个，使用js的shift方法模拟出队
            
            // 如果这个节点是我们临时塞的占位节点，就无需遍历它的下一层了，所以加个判断
            if(current !== placeHolder){ // 如果不是我们塞的占位节点的话
                // 遍历下一层
                q.push(current.left ? current.left : placeHolder) // 如果没有左子树，给塞一个占位节点
                q.push(current.right ? current.right : placeHolder) // 如果没有右子树，给塞一个占位节点
            }
            // 临时数组保存这一层的值
            list.push(current.val)
            size--
        }
        // 检查当前层是否符合对称要求
        // 如果本层不符合对称要求，直接返回false
        if( !check(list) ) return false // 所以当有一层不符合对称的要求，程序直接就终止了，后序的层就不用判断了
    }
    
    return true // 如果每一行都校验通过了，就返回true
    
    // 判断 左右两边是否对称
    function check(list){
        let i = 0;
        let j = list.length -1 
        
        while(i<j){
            if(list[i] !== list[j]) return false
            i++;
            j--;
        }
        
        return true
    }
    
}

时间复杂度O(n)：时间复杂度：在层序遍历过程中，每个节点最多入队一次，同时在 check 检查对称性过程中，每层只会被检查一次。

空间复杂度O(n)

代码2 递归检测对称性

/*
使用递归检测对称性
如何定义两棵子树 a 和 b 是否 “对称” ？
当且仅当两棵子树符合如下要求时，满足 “对称” 要求：
1. 两棵子树根节点值相同；
2. 两颗子树的左右子树分别对称，包括：
    2.1 a 树的左子树与 b 树的右子树相应位置的值相等
    2.2 a 树的右子树与 b 树的左子树相应位置的值相等

*/
function isSymmetrical(pRoot)
{
    return check(pRoot, pRoot)
    
    function check(root1, root2){
        // 出口
        if(root1 === null && root2 === null) return true  // 两个值都为空，符合对称要求
        if(root1 === null || root2 === null) return false // 一个值为null 另一个值不为null时，不符合对称要求 返回false
        if(root1.val !== root2.val) return false // 两个值不相等 不符合对称要求，返回false
        
        return check(root1.left, root2.right) && check(root1.right, root2.left)
        
    }
}

时间复杂度O(n)：每个节点只会被检查一次

空间复杂度O(n)

题目来源

JZ28 对称的二叉树