LeetCode 101.对称二叉树 - JavaScript

题目描述:给定一个二叉树,检查它是否是镜像对称的。

# 题目分析

下面这种二叉树就是镜像对称的,符合题目要求:

    1
   / \
  2   2
 / \ / \
3  4 4  3

# 解法 1:递归检查

根据题目“对称”的定义,递归过程如下:

  • 对称节点的 val 是否相同
  • 依次递归对称节点的 left1 和 right2、right1 和 left2(结合上面的例子更好理解)

代码实现如下:

// ac地址:https://leetcode-cn.com/problems/symmetric-tree/
// 原文地址:https://xxoo521.com/2020-02-16-symmetric-tree/

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
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)
  );
}

时间复杂度是 O(N),空间复杂度是 O(N)。因为最坏情况下,树是线性的。

# 更多资料