SOURCE

// 思路
// 递归实现思路
// 注意 需要先处理孩子节点的都适用后序遍历
// 因为后序遍历特性使其先遍历左右孩子最后才处理中间节点
// 本体关键不是比较 左右节点 而是 同步对比 根节点 的 左子树 和 右子树 是否能翻转得到对方
// 层序遍历实现思路
// 队列中注意按照对称位置装入节点

class Node {
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

let n2 = new Node(2, null, null);
let n2_2 = new Node(2, null, null);
let n1 = new Node(1, null, n2);
let n1_2 = new Node(1, n2_2, null);
let n4 = new Node(4, null, null);
let n4_2 = new Node(4, null, null);
let n3 = new Node(3, n4, n1);
let n3_2 = new Node(3, n1_2, n4_2);
let root = new Node(5, n3, n3_2);

// 递归实现
function fn(root) {
    // 比较 左右子树
    function 对比(left, right) {
        // 递归出口 有一个条件不满足 表示对称位置子树不等 根节点左右子树就不对称
        if (left == null && right == null) {
            // 对称位置 均为空 因为无子节点可遍历 说明当前 对称位置节点 相等
            return true
        } else if (left == null || right == null) {
            // 排除 对称位置 都为空的情况 一个为空 另一个不为空 说明不等
            return false
        } else if (left.value != right.value) {
            // 排除了 对称位置 为空的情况 值不相等 说明不等
            return false
        }
        // 对称位置 均不为空 且 值相等 则 继续递归遍历子节点
        // 用后序遍历 先判断子树是否对称
        let 外侧 = 对比(left.left, right.right)
        let 内侧 = 对比(left.right, right.left)
        // 外侧 与 内侧 都相等时 包含当前节点的子树才是对称的
        return 外侧 && 内侧
    }
    return 对比(root.left, root.right)
}

// 验证
console.log('递归实现', fn(root)) // true

// 层序遍历实现
function fn2(root) {
    let queue = [] // 辅助队列
    // 将要对比的 对称位置节点 装入
    queue.push(root.left)
    queue.push(root.right)
    while (queue.length) {
        let 左节点 = queue.shift()
        let 右节点 = queue.shift()
        if (左节点 == null && 右节点 == null) {
            // 对称位置节点都为空 说明相等 跳过执行下一层遍历
            continue
        }
        if (左节点 == null || 右节点 == null || 左节点.value != 右节点.value) {
            // 对称位置节点有一个为空 或 对称位置节点值不同 说明 二叉树 不对称
            return false
        }
        // 对称位置节点相同 则按 对称位置 装入其下一层节点
        queue.push(左节点.left)
        queue.push(右节点.right)
        queue.push(左节点.right)
        queue.push(右节点.left)
    }
    // 遍历完都未返回false 说明整颗二叉树对称
    return true
}

// 验证
console.log('层序遍历实现', fn2(root)) // true