leetcode: 对称二叉树

题目描述

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例1：

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

示例2：

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

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

题目地址：对称二叉树

思路

遍历每一个节点的时候，如果我都可以通过某种方法知道它对应的对称节点是谁，这样的话我直接比较两者是否一致就行了。

因此想法是两次遍历，第一次遍历的同时将遍历结果存储到哈希表中，然后第二次遍历去哈希表取。这种方法可行，但是需要 N 的空间（N 为节点总数）。我想到如果两者可以同时进行遍历，是不是就省去了哈希表的开销。

给定一个数组，检查它是否是镜像对称的。例如，数组 [1,2,2,3,2,2,1] 是对称的。

左子树和右子相等，也就是说要递归的比较左子树和右子树。 我们将根节点的左子树记做 left，右子树记做 right。比较 left 是否等于 right，不等的话直接返回就可以了。 如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点。

代码：

var isSymmetric = function(root) {
    if (!root) return true;
    return __isSymmetric(root.left, root.right);
};

function __isSymmetric(t1, t2) {
    if (!t1 && !t2) return true;
    if (!t1 || !t2) return false;
    return (
        t1.val === t2.val &&
        __isSymmetric(t1.left, t2.right) &&
        __isSymmetric(t1.right, t2.left)
    );
}

总结

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。