[LeetCode] Easy - 100 Same Tree

▶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.

 

▶예제

Input: p = [1,2,3], q = [1,2,3]
Output: true

Input: p = [1,2], q = [1,null,2]
Output: false

Input: p = [1,2,1], q = [1,1,2]
Output: false

728x90

▶풀이

나는 각 트리의 값들을 직접 저장해서 비교하는 방식을 사용했다.이때 preorder를 사용해서 값을 저장하고 좌측으로 가도록 했고 p, q 둘 다 preorder를 돌렸다.그다음에 answer를 두 개로 나누어서 값을 비교해서 같다면 True를 return 하도록 했다.

 

[1, 1], [1, null, 1]의 경우에 같은 결과가 나와서 처음에는 실패를 했다.그래서 root가 None일 때 answer에도 None을 넣어주는 방식으로 하니 정답이 나왔다.

# 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:
        self.answer = []
        self.preorder(p)
        cnt = len(self.answer)
        self.preorder(q)

        if self.answer[:cnt] == self.answer[cnt:]:
            return True
        else:
            return False

    def preorder(self, root):
        if root is None:
            self.answer.append(None)
            return
        self.answer.append(root.val)
        self.preorder(root.left)
        self.preorder(root.right)

이렇게 푸니까 answer이라는 list를 사용해서 그런지 공간복잡도 측면에서는 효율이 좋지 못했다.

다른 사람이 푼 방식을 보니, 바로 재귀를 이용해서 비교하는 방식을 사용했었다.

그렇게 하면 공간복잡도도 좋게 나오는 것 같은데, 나는 재귀를 잘하지 못해서, 공부 좀 해봐야겠다.