判断是否为对称二叉树

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

TreeNode

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

递归解法

• 简洁明了，美丽大方
• true
  • 都为null
  • 值相等
• false
  • 一方为null,另一方不为null
  • 值不相等

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
    if (root === null) {
        return true
    }

    const judge = (r1, r2) => {
        if (r1 === r2 && r2 === null) {
            return true
        }
        if (r1 === null || r2 === null) {
            return false
        }
        return r1.val === r2.val && judge(r1.left, r2.right) && judge(r1.right, r2.left)
    }

    return judge(root.left, root.right)
};

中序遍历解法

如果是对称的，则中序遍历结果数组一定是对称的

中序遍历规则：左根右

上图是一种特殊情况:其中序遍历结果[2,2,1,2,2]但不对称，此时需要对比节点所在层数,[3,2,1,3,2]，所以得出下面的代码

var isSymmetric = function (root) {
    if (root === null) {
        return true
    }
    const res = [] // 中序遍历结果
    const level = [] // 存放每个值所在的层数
    const midTravsere = (root, deep) => {
        if (!root) {
            return
        }
        midTravsere(root.left, deep + 1)
        res.push(root.val)
        level.push(deep)
        midTravsere(root.right, deep + 1)
    }
    midTravsere(root, 1)

    // 左右镜像节点进行对比，如果值不一样或者值一样层数不一样都为false
    for (let i = 0, j = res.length - 1; i < j; i++ , j--) {
        if (res[i] !== res[j] || level[i] !== level[j]) {
            return false
        }
    }
    return true
};

层序遍历

...未完待续