leetcode - Tree - Symmetric Tree

 

이번 문제는 1개의 tree를 인자로 받아 대칭인지 판단하는 문제입니다.

 

대칭트리의 경우에는, 트리의 왼쪽부분은 왼쪽 우선으로, 오른쪽 부분은 오른쪽 우선으로 탐색 시 만나는 값의 순서가 같습니다.

 

그렇기 때문에, 저는 아래와 같이 풀이했습니다.

 

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

    def isSymmetric(self, root: TreeNode) -> bool:
        if root == None: return True
        left_list = [root.val]
        right_list = [root.val]

        self.searchPriorLeft(root.left, left_list)
        self.searchPriorRight(root.right, right_list)
        
        if len(right_list) != len(left_list): return False

        for i in range(len(right_list)):
            if right_list[i] != left_list[i]: return False
        return True

    def searchPriorLeft(self, root: TreeNode, list):
        if root == None:
            list.append(None)
            return True
        list.append(root.val)
        if root.left == None and root.right == None: return True
        self.searchPriorLeft(root.left, list)
        self.searchPriorLeft(root.right, list)

    def searchPriorRight(self, root: TreeNode, list):
        if root == None:
            list.append(None)
            return True
        list.append(root.val)
        if root.left == None and root.right == None: return True
        self.searchPriorRight(root.right, list)
        self.searchPriorRight(root.left, list)

 

감사합니다.