LeetCode-101.对称二叉树

发表于 分类于

题目描述

示例1

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

示例1

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

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100

题解

方法1：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isSymmetric(_ root: TreeNode?) -> Bool {
  guard let root = root else {
    return true
  }
  
  func dfs(_ left: TreeNode?, _ right: TreeNode?) -> Bool {
    if left === nil && right === nil {
      return true
    }
    if left === nil || right === nil || left!.val != right!.val {
      return false
    }
    return dfs(left?.left, right?.right) && dfs(left?.right, right?.left)
  }
  
  return dfs(root.left, root.right)
}

方法2：遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func isSymmetric(_ root: TreeNode?) -> Bool {
  guard let root = root else {
    return true
  }
  var queue = [root.left, root.right]
  while !queue.isEmpty {
    let left = queue.removeFirst()
    let right = queue.removeFirst()
    if left === nil && right === nil {
      continue
    }
    if left === nil || right === nil || left!.val != right!.val {
      return false
    }
    queue.append(left?.left)
    queue.append(right?.right)
    
    queue.append(left?.right)
    queue.append(right?.left)
  }
  return true
}