Same Tree - LeetCode

Problem

1. input: 이진 트리 p, q
2. output: 두 이진 트리가 같은지 Boolean 리턴
   • The number of nodes in both trees is in the range [0, 100].
   • 104 <= Node.val <= 104

Idea

오랜만에 트리 탐색 문제가 나왔다. 기억을 되살리겸 순회를 통해 두 트리를 비교하는 쪽으로 방향을 잡았다. 한가지 주의할 점이 있다면, 무작정 순회를 통해 비교를 할경우 [1, 1, null]과 [1, null, 1]을 구분하지 못한다. 때문에, 각 노드의 depth나 level을 붙여줘야 한다 → Sol1

정석적인 풀이는 재귀를 통해 각 노드를 하나씩 비교하는 것이다 → Sol2

Solution

1. 전위 순회

   각 노드를 전위 순회하며 문자열 리턴

   (이때, ‘level : 노드 값’)

   class Solution {
       fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
           if (p == null && q == null) return true
           if (p == null || q == null) return false
           return preOrder(p) == preOrder(q)
       }
   
       fun preOrder(p: TreeNode?, level: Int = 1): String {
           if (p == null) return ""
           return preOrder(p.left, level+1) + level.toString() + ":" + p.`val`.toString() + "," + preOrder(p.right, level+1)
       }
   }
   

   시간 복잡도: 트리 순회 = n

   

2. 재귀

   • 노드의 값 서로 비교

   재귀

   • 왼쪽 자식 비교
   • 오른쪽 자식 비교

   class Solution {
       fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
           if (p == null && q == null) return true
           if (p == null || q == null || p.`val` != q.`val`) return false
           return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
       }
   }
   

   시간 복잡도: 트리 순회 = n

   

Point

1. 트리의 순회는 대부분 재귀를 이용 → 조건에 따라 return 값을 정하는 것이 핵심