LeetCode/Symmetric Tree

( 블로그 기사 의 전재)

[ h tps : // / ㅇ t 여기. 이 m / p 로b ㎇ ms / sy めめ t t t 에에 / ]

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

마지막 기사의 Same Tree 다음에 바이너리 트리를 다룬 문제.
이번에는 Symmetric, 즉 좌우 대조의 도형인지 어떤지를 판정합니다.
보너스 포인트를 준다는 것이며, recursive 해법과 iterative 해법을 모두 찾아 봅시다.

해답·해설

해법 1

recursive 해법.

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

class Solution:
    def isSymmetric(self, root):
        if not root:
            return True
        else:
            return self.isMirror(root.left, root.right)
    def isMirror(self, left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val == right.val:
            outPair = self.isMirror(left.left, right.right)
            inPiar = self.isMirror(left.right, right.left)
            return outPair and inPiar
        else:
            return False

두 함수를 정의하고 있지만 이전 Same Tree와 달리 바이너리 트리가 하나뿐이므로 트리가 없으면 True를 반환하는 프로세스를 끼고 있습니다.
isMirror 함수의 처리는 Same Tree와 비슷하지만,
(좌측 트리의 좌측과 우측의 트리의 우측), (우측의 트리의 좌측과 우측의 트리의 좌측)의 각각이 동일한지 어떤지를 판정하도록 합니다.

해법 2

Iterative 해법.
모처럼이므로 전회 기사에서도 취급한, deque형을 사용해 써 봅니다.

from collections import deque
class Solution:
    def isSymmetric(self, root):
        if not root:
            return True

        deq = deque([(root.left, root.right),])
        while deq:
            t1, t2 = deq.popleft()
            if not t1 and not t2:
                continue
            elif (not t1 or not t2) or (t1.val != t2.val):
                return False

            deq.append((t1.left, t2.right))
            deq.append((t1.right, t2.left))

        return True

이하에 Same Tree 때의 코드를 재게재합니다. 미묘한 차이밖에 없는 것을 알 수 있을까 생각합니다.

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