zhangdizhangdi

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)

ts
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))

方法：广度优先【todo⌛️】

BFS