(LeetCode) Symmetric Tree

Symmetric Tree

  • Explore : Interview > Top Interveiw Questions > Easy Collection
  • 분류 : Trees
  • 난이도 : Easy

Problem

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1

1
2
Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2

1
2
Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

Solution - Recursive

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun isSymmetric(root: TreeNode?): Boolean {
if (root == null) {
return true
}
return recursive(root.left, root.right)
}

fun recursive(left: TreeNode?, right: TreeNode?): Boolean {
if (left == null && right == null) {
return true
}
else if (left == null || right == null) {
return false
}
else if (left.`val` != right.`val`) {
return false
}
return recursive(left.left, right.right) && recursive(left.right, right.left)
}
}

Solution - Iterative

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun isSymmetric(root: TreeNode?): Boolean {
if (root == null) {
return true
}
var queue: Queue<Pair<TreeNode, TreeNode>> = LinkedList()
queue.add(Pair(root, root))

while (queue.isNotEmpty()) {
var node = queue.poll()
var left = node.first
var right = node.second
if (left != null || right != null) {
if (left != null && right != null && left.`val` == right.`val`) {
queue.add(Pair(left.left, right.right))
queue.add(Pair(left.right, right.left))
} else {
return false
}
}
}
return true
}

}

Point of Thinking

  • 문제에서 재귀와 반복을 다 구현해보는 게 추천되어서 두 가지 방법으로 풀이해보았다.
  • 재귀든 반복이든 대칭트리를 증명하는 규칙은 아래와 같다.
      1. left / right가 둘 다 null이면 leaf node가 없으므로 true
      1. left와 right 둘 중 하나라도 null이면 false
      1. left와 right의 값이 다르면 false
      1. 그 외 조건은 다시 한 번 재귀 혹은 반복
  • 대칭트리이므로 파라미터가 조금 독특하게 느껴질 수도 있다. 휴먼에러에 주의하자.