对称二叉树

问题

给定一棵二叉树的根节点 root，判断这棵树是否是镜像对称的。

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

上面这棵树是对称的，返回 true。

    1
   / \
  2   2
   \   \
   3    3

上面这棵树不对称，返回 false。

解答

递归解法

// 二叉树节点定义
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

/**
 * 判断二叉树是否对称
 * @param {TreeNode} root
 * @return {boolean}
 */
function isSymmetric(root) {
  if (root === null) return true;
  return isMirror(root.left, root.right);
}

/**
 * 判断两棵树是否互为镜像
 * @param {TreeNode} left
 * @param {TreeNode} right
 * @return {boolean}
 */
function isMirror(left, right) {
  // 都为空，对称
  if (left === null && right === null) return true;
  // 只有一个为空，不对称
  if (left === null || right === null) return false;
  // 值不相等，不对称
  if (left.val !== right.val) return false;

  // 递归比较：左的左 vs 右的右，左的右 vs 右的左
  return isMirror(left.left, right.right) && isMirror(left.right, right.left);
}

迭代解法

/**
 * 使用队列迭代判断
 * @param {TreeNode} root
 * @return {boolean}
 */
function isSymmetricIterative(root) {
  if (root === null) return true;

  const queue = [root.left, root.right];

  while (queue.length > 0) {
    // 每次取出两个节点比较
    const left = queue.shift();
    const right = queue.shift();

    // 都为空，继续下一对
    if (left === null && right === null) continue;
    // 只有一个为空，或值不等
    if (left === null || right === null) return false;
    if (left.val !== right.val) return false;

    // 按镜像顺序入队
    queue.push(left.left, right.right);
    queue.push(left.right, right.left);
  }

  return true;
}

测试

// 构建对称树: [1,2,2,3,4,4,3]
const symmetricTree = new TreeNode(
  1,
  new TreeNode(2, new TreeNode(3), new TreeNode(4)),
  new TreeNode(2, new TreeNode(4), new TreeNode(3))
);

// 构建非对称树: [1,2,2,null,3,null,3]
const asymmetricTree = new TreeNode(
  1,
  new TreeNode(2, null, new TreeNode(3)),
  new TreeNode(2, null, new TreeNode(3))
);

console.log(isSymmetric(symmetricTree)); // true
console.log(isSymmetric(asymmetricTree)); // false

关键点

• 对称的本质是左右子树互为镜像
• 镜像比较：左子树的左 对应 右子树的右，左子树的右 对应 右子树的左
• 递归终止条件：两个都为空返回 true，只有一个为空返回 false
• 迭代解法用队列成对存取节点，按镜像顺序入队
• 时间复杂度 O(n)，空间复杂度 O(n)