[Leetcode] 100. Same Tree_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '100. Same Tree'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해 준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Same Tree' 알고리즘 문제

 

STEP 2. 'Same Tree' 코드(code)

 

STEP 3. 'Same Tree' 해설

 

STEP 4. 'Same Tree' solution

 

반응형

 

STEP 1. 'Same Tree' 알고리즘 문제

 

Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

 

두 이진 트리 p와 q의 루트가 주어졌을 때, 두 트리가 동일한지 확인하는 함수를 작성하세요.
두 이진 트리가 구조적으로 동일하고, 모든 노드의 값이 동일할 때 두 트리는 동일하다고 판단합니다.

 

Constraints:

• The number of nodes in both trees is in the range [0, 100].
• -104 <= Node.val <= 104

 

---

STEP 2. 'Same Tree' 코드(code)

 

■ Runtime: 0ms Beats 100.00%
■ Memory: 17.93 MB Beats 21.39%

 

# 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:
        def dfs(n1, n2):
            # Both are None
            if not n1 and not n2:
                return True

            # One of them are None
            if not n1 or not n2:
                return False

            # Both values are not same
            if n1.val != n2.val:
                return False
            
            left = dfs(n1.left, n2.left)
            right= dfs(n1.right, n2.right)
            return left and right
        
        return dfs(p, q)

---

STEP 3. 'Same Tree' 해설

 

각 노드를 재귀적으로 비교하는 방식으로, 두 트리가 동일한지 확인하는 함수를 구성했습니다.
두 노드가 모두 None이면 더 이상 비교할 것이 없으므로 True를 반환합니다.
한쪽만 None이거나, 두 노드의 값이 다르면 구조나 값이 다른 것이므로 False를 반환합니다.

그렇지 않다면, 왼쪽 서브트리와 오른쪽 서브트리에 대해 각각 재귀적으로 비교한 결과를 and 연산으로 결합해 최종 결과를 반환합니다.

 

 

STEP 4. 'Same Tree' solution

 

추가적으로, Leetcode에서 제공해 준 solution 코드를 살펴보겠습니다.

 

■ Runtime: 2ms Beats 3.07%
■ Memory: 17.70MB Beats 91.26%

 

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        
        if p and q and p.val == q.val:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        
        return False

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '100. Same Tree'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.