Home Same Tree
Post
Cancel

Same Tree

Leetcode Problem

Same Tree

두 binary tree가 같은지를 비교하는 문제입니다.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        def preorder(p: Optional[TreeNode], q: Optional[TreeNode]):
            if not p and not q:
                return True
            elif (not p and q or p and not q) or p and q and p.val != q.val:
                print("false")
                return False
            else:
                return preorder(p.left, q.left) and preorder(p.right, q.right)
        return preorder(p, q)

not p and not q일 경우에 대해 어떻게 처리해야 할지를 몰라 결국 좀 찾아보면서 문제를 해결했습니다. false일 경우를 먼저 생각해냈지만, 이 부분을 제외하고 True일 경우



1
2
3
4
5
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p == None or q == None:
            return p == q
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

solution에서 본 깔끔한 풀이입니다.
따로 내부함수를 만들지 않고 그 자체로 재귀를 처리하는 방법을 고민했었는데, 이런 방법이 있었습니다.
뿐만 아니라, None type을 처리하는 방식이 훨씬 깔끔합니다.





참고

This post is licensed under CC BY 4.0 by the author.