[LeetCode 해석 및 풀이] 100. Same Tree (같은 트리)

LeetCode 문제 해석 및 풀이 방법

 

문제 100. 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가 주어졌을 때 두 개의 트리가 같은지 아닌지 체크하는 함수를 작성하시오,

 

두 개의 이진트리는 구조적으로 동일하고 노드가 동일한 값을 갖는 경우 동일한 것으로 간주됩니다.

 

제한조건

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

 

입출력 예

true

false

false

입력	출력
p = [1,2,3], q = [1,2,3]	true
p = [1,2], q = [1,null,2]	false
p = [1,2,1], q = [1,1,2]	false

 

 

해답 및 해설

파이썬 (Python)

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def isSame(p, q):
            if None in (p, q):
                if p == q:
                    return True
                else:
                    return False
            
            if not p.val == q.val:
                return False

            is_left_same = isSame(p.left, q.left)
            if not is_left_same:
                return False

            is_right_same = isSame(p.right, q.right)
            if not is_right_same:
                return False
            
            return True
        
        return isSame(p, q)

 

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

 

재귀에서 최대한 반복을 없애려고 위처럼 했는데 생각해보니 걍 아래처럼 했어도 어련히 됐다.