[대칭 트리]Leetcode Symmetric Tree Python

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Symmetric Tree
등급: EASY

오늘도 EASY 등급에 힘겨워하는 나...

<코드>

우선, 이건 내가 생각해서 적은 코드가 아니다. 유튜브를 보고 아이디어를 받았다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        if not root:
            return True
        
        return self.check(root.left, root.right)
        
    # left subtree, right subtree
    def check(self, left, right):
        #if both nodes are null
        if not left and not right:
            return True
        # if both nodes have value
        elif left and right:
            return left.val == right.val and self.check(left.right, right.left) and self.check(left.left, right.right)
        # if one node has value, and one is null
        else:
            return False
            
        """
        :type root: TreeNode
        :rtype: bool
        """

<논리>

isSymmetric 함수에서는, root가 비었는지 안 비었는지만 확인한다. root에 node가 없다면 symmetric 대칭인 것이며, 있다면 check(left, right) 함수를 통해 확인해준다.

 

check(left, right) 함수는 left에는 왼쪽 node를, right에는 오른쪽 node의 입력을 요구한다. 처음 if는, issymmetric과 같이 둘 다 비어있는 경우 당연히 True를 반환한다. 두 번째 if or elif의 경우, 두 node에 value가 있다면 총 세 가지를 확인한다. 첫 번째는 두 value를 비교함으로써 False 또는 True가 나올 것이며, 두 번째 세 번째는, left와 right node들의 다음 node들을 확인해준다. 이렇게 재귀 호출이 됨으로써 전체 트리의 확인이 가능해진다.

 

마지막 else는 한 node는 값이 없고 한 node는 값이 있는 경우 false를 반환해준다.

 

두번째의 elif 같은 경우의 한 가지 논리가 숨겨져 있는데, 그것은 왼쪽 트리의 왼쪽과 오른쪽 트리의 오른쪽의 값을 비교해줘야 한다는 것이다. 다른 말로 하자면, 왼쪽 트리의 오른쪽과 오른쪽 트리의 왼쪽 값을 비교해야 한다. 그래서 내가 적은 left와 right는 leftsubtree와 rightsubtree로 생각한다면 더 이해하기 쉬울 것이다. (왼쪽-왼쪽, 오른쪽-오른쪽의 반대로 비교하는 것)

<코드 - iterative>

class Solution(object):
    def isSymmetric(self, root):
        if root is None:
            return True
        stack = [root, root]
        while len(stack) != 0:
            left = stack.pop(0)
            right = stack.pop(0)
            if not left and not right:
                continue
            elif left and right:
                if left.val == right.val:
                    stack.extend([left.left, right.right, left.right, right.left])
                else:
                    return False
            else:
                return False
        return True

Recursive과 거의 똑같은 방식이다. 다른 점은 while loop을 통한 left와 right를 stack에 더해서 left 서브트리와 right 서브 트리를 비교하는 것이다.

 

한 가지 주의할 점이 있다면 if not left and not right의 경우 recursive이 아니기 때문에 return True가 아닌 continue를 하자.

 

이 경우, recursive의 경우가 iterative보다 빠를 수밖에 없는 것이, while loop가 모든 node를 비교하게 만들고 있다.

 

밑에는 set()을 활용함으로써 recursive와의 속도가 별 차이 나지 않는다.

  def isSymmetric(self, root):
      if root is None:
          return True
      stack = [(root.left, root.right)]
      while stack:
          left, right = stack.pop()
          if not left and not right:
              continue
          if left is None or right is None:
              return False
          if left.val == right.val:
              stack.extend([(left.left, right.right), (left.right, right.left)])
          else:
              return False
      return True

<총평>

 

Happy coding!

Symmetric Tree - LeetCode