LeetCode 풀기 - 101. Symmetric Tree

101. Symmetric Tree

https://leetcode.com/problems/symmetric-tree/

Symmetric Tree - LeetCode

문제)

솔루션1) iterative

• 스태과 큐 두 개의 자료 구조를 준비
• BFS를 적용하여 트리의 한 depth를 queue 자료 구조에 넣고
• queue를 전체 pop해서 stack에 node를 추가
• stack의 node의 value를 가운데를 기준으로 잘라서 대칭이 되는지 확인
• 대칭이되면 트리의 다음 뎁스로 넘어가서 위 과정을 반복

class Solution:
    def isSymmetric(self, root):
        queue = []
        stack = []

        queue.append(root)

        while True:
            while queue:
                node = queue.pop()
                if node:
                    stack.append(node.left)
                    stack.append(node.right)

            if len(stack) == 0:
                break

            mid = len(stack) // 2
            left_values = [node.val if node else None for node in stack[:mid]]
            right_values = [node.val if node else None for node in stack[mid:]][::-1]

            if left_values != right_values:
                return False

            while stack:
                queue.append(stack.pop())

        return True