手帐 Blog

主题

复盘 · LC 101 对称二叉树 ​

题目 ​

题意 ​

判断一棵二叉树是否轴对称：以根为镜面，左子树与右子树互为镜像（结构与对应节点值都相同）。

边界：空树（通常视为对称）、单节点、只有一侧子树、值相同但结构不对称、节点值为 0。

涉及算法 ​

标签一句话
递归镜像同时比「左的左 vs 右的右」「左的右 vs 右的左」
队列成对比较BFS 每次取一对节点，按镜像顺序入队

教程对照：17 · 二叉树递归经典。

评价我的解法 ​

我的代码（摘自 101-对称二叉树/index.js，去掉大段注释与本地测例；保留实际执行路径）：

javascript
function deep(root, val) {
  if (!root) {
    return 0;
  }
  const leftValue = deep(root.left);
  const rightValue = deep(root.right);
  return Math.max(leftValue, rightValue) + 1;
}

function reverse(arr) {
  const newArr = JSON.parse(JSON.stringify(arr));
  return newArr.reverse();
}

var isSymmetric = function (root) {
  let isSymmetricResult = true;
  const deepVal = deep(root, 1);
  const resArr = [];
  const numArr = [];
  for (let i = 0; i < deepVal; i++) {
    if (i === 0) {
      resArr.push(root);
      numArr.push(root.val);
    } else {
      const arrLen = resArr.length;
      for (let j = 2 ** (i - 1) - 1; j < arrLen; j++) {
        let left = resArr[j].left;
        if (!left) {
          left = "*";
        }
        let right = resArr[j].right;
        if (!right) {
          right = "*";
        }
        resArr.push(left, right);
        if (left?.val) {
          numArr.push(left.val);
        } else {
          numArr.push(left);
        }
        if (right?.val) {
          numArr.push(right.val);
        } else {
          numArr.push(right);
        }
      }
    }
  }
  const res2Arr = [];
  let i = 0;
  while (true) {
    const curArrLength = 2 ** i;
    if (numArr.length < curArrLength) {
      break;
    }
    res2Arr.push(numArr.splice(0, curArrLength));
    i++;
  }
  for (const item of res2Arr) {
    const reverseItem = reverse(item);
    const str = item.join("");
    const reverseStr = reverseItem.join("");
    if (str !== reverseStr) {
      isSymmetricResult = false;
      break;
    }
  }
  return isSymmetricResult;
};

思路方向能理解：按层铺开，缺孩子用 "*" 占位，再看每一层是否回文——「层对称 ≈ 树对称」在完全铺满占位时理论上说得通。

但实现偏糙、有坑：

  1. if (left?.val) 把 0 当假：节点值为 0 时会把整个节点对象推进 numArr，join 结果不可控。
  2. join("") 比较：多位数会撞车（如 [11,1] 与 [1,11] 都是 "111"），假阳性风险。
  3. 对 "*" 父节点继续 .left：更深且含空位时可能抛错；依赖「深度刚好、测例没踩」很脆。
  4. 复用了 104 的 deep、深拷贝 reverse、大量下标魔法——复杂度与可读性都远差于「成对递归」。

本地测例是不对称树，能打出 false，但不足以证明通用正确。

最佳题解 ​

递归镜像比较：

javascript
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function (root) {
  function mirror(a, b) {
    if (!a && !b) return true;
    if (!a || !b) return false;
    return (
      a.val === b.val &&
      mirror(a.left, b.right) &&
      mirror(a.right, b.left)
    );
  }
  return mirror(root, root);
  // 或：return !root || mirror(root.left, root.right);
};
  • 时间 O(n)，空间 O(h)。
  • 为何更优：定义即「左右互为镜像」，无层展开、无字符串、无 0 / 多位数坑。

队列版（同一思想，迭代）：

javascript
var isSymmetric = function (root) {
  if (!root) return true;
  const q = [root.left, root.right];
  while (q.length) {
    const a = q.shift();
    const b = q.shift();
    if (!a && !b) continue;
    if (!a || !b || a.val !== b.val) return false;
    q.push(a.left, b.right, a.right, b.left);
  }
  return true;
};

关联题目 ​

题为何相关
100. 相同的树成对比较节点的近亲题
104. 二叉树的最大深度今日刚写的深度递归可复用心智
226. 翻转二叉树「镜像」另一面：主动翻转

一句话带走 ​

对称树：别铺层再拼字符串——同时比 (左,右)，交叉递归左右孩子。