解题步骤

  1. 分：获取两个树的左子树和右子树
  2. 解：递归地判断树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像
  3. 合：如果上述都成立，且根节点值也相同，两个树就镜像

通过分而治之思想实现

  • 时间复杂度：O (n)

  • 空间复杂度：O (h)

    1. function isSymmetric(root) {
    2.   if (!root) return true;
    4.   const isMirror = (l, r) => {
    5.       if (!l && !r) return true;
    7.       if (!l || !r) return false;
    9.       if (l.val === r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left)) {
    10.           return true;
    11.       }
    13.       return false;
    14.   };
    16.   return isMirror(root.left, root.right);
    17. }

    代码中利用递归遍历了树的所有节点，所以时间复杂度是 O (n) ，而空间复杂度是 O (h) h 是树的高度，因为存在调用堆栈占据了空间。