LeetCode 100(Same Tree, Python)

1. 문제 링크

• https://leetcode.com/problems/same-tree/

Same Tree - LeetCode

2. 문제 설명

• 이진 트리 p, q가 주어졌을 때, 두 트리가 같은 tree인지 판단
  • 같다의 정의: 구조적으로 동일(structurally identical)하고, node가 동일한 value를 가지고 있을 때.
  • 예시 1) 아래 두 트리는 동일하므로 true를 반환 
    •         1
             / \
            2   3
    •         1
             / \
            2   3 
  • 예시 2) 아래 두 트리는 동일하지 않으므로 false를 반환
    •         1
             / \
            2   3 
    •         1
             / \
            3   2 

3. 처음 풀이

• 처음에 너무 양아치같은 아이디어가 생각이 나서 바로 작성했고, 가볍게 통과
  • 그냥 두 tree를 문자열로 반환한 값이 동일하면 같은 tree일 테니, str(q)와 str(p)가 같은지 비교 
  • 역시나 runtime이 21.55% beats로 결과가 좋진 않았고, tree관점에서 다시 풀이

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        return str(p) == str(q)

• 트리 문제를 푸는게 익숙하지 않아서, 우선 케이스를 나눠서 풀이함
  • True, False를 반환하는 check함수를 만든 뒤, 
  • p는 None인데 q가 None이 아니거나 그 반대 케이스일 때는 False 반환
  • p와 q가 둘다 None이면 True 반환
  • 둘다 None이 아닐 때, p.val과 q.val이 다르면 False 반환
  • 위 세가지 케이스에 포함되지 않는 경우, p와 q의 왼쪽 node 비교, p와 q의 오른쪽 node 비교한 boolean값을 반환 
• runtime은 잘 나왔으나, 뭔가 모든 케이스를 일일히 파악해야 해서 깔끔한 풀이라 생각이 안들어서 아쉬웠음
• 그리고 check함수를 만들지 않고 바로 recursive하게 짤 수도 있을 것 같다는 생각이 듦 → 다른 사람 풀이 참고

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def check(p,q):
            if p is None and q is not None:
                return False
            elif q is None and p is not None:
                return False
            elif p is None and q is None:
                return True
            elif p.val != q.val:
                return False
            else:
                return check(p.left,q.left) and check(p.right,q.right)
        return check(p,q)

  

4. 다른 풀이

• 보편적으로 많았던, 다른 사람들의 풀이를 참고 
• 로직은 거의 비슷하나, check함수를 따로 두지 않고, isSameTree로 바로 recursive하게 짠 깔끔한 코드 
  • 우선 언제 True이고 언제 False인지를 정의한후, 그 케이스에서 바로 반환이 안될 때, 
    • p와 q의 left, p와 q의 right, p.val q.val 각각의 boolean값의 and 를 반환

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None and q is None:
            return True
        elif p is None or q is None:
            return False 
        
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right,q.right)

 

5. 배운 점

• 트리에서는 재귀를 적극적으로 활용할 필요가 있다. 
• 트리가 언제 같아지고 달라지는지 조건을 파악하고, 해당 조건으로 바로 True, False가 안나올 시, 재귀를 써서 왼쪽, 오른쪽 노드를 탐색한다!