101.对称二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    // 先层序遍历，拿到每一层的节点数，再比较
    let levelArr = [] // 二维数组，每一项代表每一层的节点数组
    let queue = []
    queue.push(root)
    while (queue.length) {
        let len = queue.length // 每一层的节点数
        let levelNodes = []
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            // 注意记录null节点
            if (node === null) {
                levelNodes.push(null)
            } else {
                levelNodes.push(node.val)
                queue.push(node.left)
                queue.push(node.right)
            }
        }
        levelArr.push(levelNodes)
    }
    console.log(levelArr)
    // 比较每一层的节点是否对称
    levelArr.shift() // 根节点不用比较
    for (let i = 0; i < levelArr.length; i++) {
        let nodes = levelArr[i]
        // 每次从头尾取出节点进行比较
        while (nodes.length) {
            let head = nodes.shift()
            let tail = nodes.pop()
            if (head !== tail) {
                return false
            }
        }
    }

    return true
};

// 迭代
var check = function (u, v) {
    // 思路：左子树的左节点==右子树的右节点，左子树的右节点==右子树的左节点
    let queue = [] // 将两个结点的左右子结点按相反的顺序插入队列中
    queue.push(u)
    queue.push(v)
    while (queue.length) {
        u = queue.shift()
        v = queue.shift()
        if (!u && !v) {
            continue
        }
        if ((!u || !v) || (u.val !== v.val)) {
            return false
        }
        // 一对节点
        queue.push(u.left)
        queue.push(v.right)

        // 另一对节点
        queue.push(u.right)
        queue.push(v.left)
    }
    return true
}
var isSymmetric = function (root) {
    return check(root, root)
}


// 递归
// 两根指针
var check = (p, q) => {
    if(!p && !q) { // 遍历完了，没发现不同节点，所以返回true
        return true
    }
    if(!p || !q) {
        return false
    }
    return p.val === q.val && check(p.left, q.right) && check(p.right, q.left)
}
var isSymmetric = function (root) {
    return check(root, root)
}