101. 对称二叉树 🟩

题目

LeetCode 简单

题目

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

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

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

题解

方法：递归

DFS 深度优先 递归

时间复杂度：O(n)
空间复杂度：O(n)

function isSymmetric(root: TreeNode | null): boolean {
  const isSame = (left: TreeNode | null, right: TreeNode | null) => {
    console.log('left', left?.val, 'right', right?.val)

    if (!left && !right) return true
    if (
      left &&
      right &&
      left.val === right.val &&
      isSame(left.left, right.right) &&
      isSame(left.right, right.left)
    )
      return true
    return false
  }

  return isSame(root.left, root.right)
}

const p = new Tree([1, 2, 2, 3, 4, 4, 3, 5, 6, 7, 8, 8, 7, 6, 5]),
  q = new Tree([1, 2, 2, null, 3, null, 3])

console.log('🌰', isSymmetric(p.root))
console.log('🌰', isSymmetric(q.root))

方法：迭代

在 JS 中，既可以用栈（pop() 弹出尾部，做深度优先遍历 DFS），也可以用队列（shift() 弹出头部，做广度优先遍历 BFS）。两者逻辑在这道题里完全通用。

时间复杂度：O(n)
空间复杂度：O(n)

// 1. 定义二叉树节点
class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

// ==========================================
// 核心算法：对称二叉树 (迭代法)
// ==========================================
var isSymmetric = function (root) {
  if (root === null) return true // 空树绝对对称

  // 初始化栈，把根节点的左孩子和右孩子作为第一对
  const stack = [[root.left, root.right]]

  while (stack.length > 0) {
    console.log(
      'stack',
      JSON.stringify(
        stack.map(pair => pair.map(node => (node ? node.val : null))),
      ),
    )

    // 弹出一对节点进行“镜像”比较
    const [leftNode, rightNode] = stack.pop()

    // 1. 两个都是 null，说明这对镜像分支走到底了，安全
    if (leftNode === null && rightNode === null) {
      continue
    }

    // 2. 一个为空另一个不为空，镜像被打破
    if (leftNode === null || rightNode === null) {
      return false
    }

    // 3. 值不相等，镜像被打破
    if (leftNode.val !== rightNode.val) {
      return false
    }

    // 走到这里说明当前的一对节点长得一样。
    // 开始【交叉配对】并压入栈中：
    // 外侧配外侧：左节点的左孩子，配上，右节点的右孩子
    stack.push([leftNode.left, rightNode.right])

    // 内侧配内侧：左节点的右孩子，配上，右节点的左孩子
    stack.push([leftNode.right, rightNode.left])
  }

  // 所有验证全部通过
  return true
}

// --- 运行测试 ---

// 树 A: 对称树[1, 2, 2, 3, 4, 4, 3]
//       1
//      / \
//     2   2
//    / \ / \
//   3  4 4  3
const treeA = new TreeNode(1)
treeA.left = new TreeNode(2, new TreeNode(3), new TreeNode(4))
treeA.right = new TreeNode(2, new TreeNode(4), new TreeNode(3))

// 树 B: 不对称树[1, 2, 2, null, 3, null, 3]
//       1
//      / \
//     2   2
//      \   \
//       3   3
const treeB = new TreeNode(1)
treeB.left = new TreeNode(2, null, new TreeNode(3))
treeB.right = new TreeNode(2, null, new TreeNode(3))

console.log('🌰 TreeA 是否对称？ (预期: true) ->', isSymmetric(treeA))
console.log('-----------------------------')
console.log('🌰 TreeB 是否对称？ (预期: false)->', isSymmetric(treeB))

执行结果

stack [[2,2]]
stack [[3,3],[4,4]]
stack [[3,3],[null,null],[null,null]]
stack [[3,3],[null,null]]
stack [[3,3]]
stack [[null,null],[null,null]]
stack [[null,null]]
🌰 TreeA 是否对称？ (预期: true) -> true
-----------------------------
stack [[2,2]]
stack [[null,3],[3,null]]
🌰 TreeB 是否对称？ (预期: false)-> false

本页目录