LeetCode/Same Tree

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 코 m / p 로b ㎇ ms / 사메 t 레에 / ]

Given two binary trees, 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.



LeetCode에서는 바이너리 트리(이분 트리)를 사용한 문제가 자주 발생하지만, 그 중 하나입니다.
두 개의 바이너리 트리가 동일한지 여부를 결정하는 문제입니다.

해답·해설

해법 1

recursion을 사용한 깔끔한 코드는 다음과 같습니다.
isSameTree(p,q) 함수를 "TreeNode 인스턴스의 p와 q가 모두 없으면 True, 둘 중 하나가 없으면 False, val이 다르면 False"로 처리하는 것으로 정의하고,
마지막으로 isSameTree(p.right,q.right)에서 Tree의 우측이 동일한 판정을, isSameTree(p.left,q.left)에서 Tree의 좌측이 동일한 판정을 하는 재귀적인 구조로 합니다. .

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

해법 2

나는 몰랐습니다만, python에는 deque라고 하는 데이터형이 있군요.
이 기사 가 상세하지만,
list형은 선두로부터 데이터를 삭제할 때에 요소의 이동이 발생하기 때문에 $O(n)$의 오퍼레이션인데, deque형은 선두로부터도 마지막미로부터도 $O(1)$로 요소 꺼내서 삭제할 수 있다는 것입니다.
그런데, 이 deque형을 사용해, Iteration으로 푸는 공식의 해법이 이하와 같습니다.

from collections import deque
class Solution:
    def isSameTree(self, p, q):
        def check(p, q):
            if not p and not q:
                return True
            if not q or not p:
                return False
            if p.val != q.val:
                return False
            return True

        deq = deque([(p, q),])
        while deq:
            p, q = deq.popleft()
            if not check(p, q):
                return False

            if p:
                deq.append((p.left, q.left))
                deq.append((p.right, q.right))

        return True

list형에서도 비슷한 코드가 됩니다만, popleft 함수는 deque만이 가능한 처리입니다.
check 함수는 해법 1에서 나온 처리와 완전히 동일합니다.
변수 deque에 동일한지 어떤지를 판정하는 TreeNode의 페어를 격납해 가고, check 함수에 의한 판정을 iterative에 실시하는 처리가 됩니다.