LeetCode 101. Symmetric Tree

 

Binary Tree가 symmetric한지 알아내는 문제이다.

 

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

Symmetric Tree - LeetCode

Follow up에서 recursive, iterative solution 각각으로 풀어보는것을 권장한다.

 

1. Recursive Solution

 

Tree형태이므로, 왼쪽과 오른쪽의 node를 비교하며 찾는다.

 

if l and r 구문의 경우, l 과 r 중 하나라도 None일 때 node.left, node.right 에서 발생할 수 있는 error를 처리하고자 적용되었다.

 

else에서 l == r인 이유는 NoneType에는 .val 값이 존재하지 않고 둘다 같은 None인지만 알아내면 되기 때문이다.

# Definition for a binary tree node.

class TreeNode:

    def __init__(self, val=0, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

class Solution:

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:

       

        if not root:

            return False

        l = root.left

        r = root.right

        def rec(l,r):

            if l and r:            

                return rec(l.left, r.right) and rec(l.right, r.left) and l.val == r.val

            else:

                return l == r

       

        return rec(l,r)

 

2. Iterative Solution

 

Iterative Solution의 경우, 코드가 좀더 복잡하다.

 

stack을 사용하여 DFS방식의 iterative solution을 만들었다.

# Definition for a binary tree node.

class TreeNode:

    def __init__(self, val=0, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

class Solution:

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:

       

        l = root.left

        r = root.right

        lstack = [l]

        rstack = [r]

        while lstack and rstack:

            lnode = lstack.pop()

            rnode = rstack.pop()

            if lnode and rnode:

                if not lnode.val == rnode.val:

                    return False

                   

                lstack.append(lnode.left)

                lstack.append(lnode.right)

                rstack.append(rnode.right)

                rstack.append(rnode.left)

            else:

                if not lnode == rnode:

                    return False

        return True

보다 효율적으로 푸는 방법으로는 하나의 stack을 활용하여 memory 사용량을 줄일 수 있다.(권장)

# Definition for a binary tree node.

class TreeNode:

    def __init__(self, val=0, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

class Solution:

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:

       

        stack = []

        if not root:

            return False

           

        stack.append([root.left, root.right])

        while(len(stack) > 0):

            left, right = stack.pop()

           

            if left and right:

                if left.val != right.val: return False

                stack.append([left.left, right.right])

                stack.append([right.left, left.right])

       

            elif left or right: return False

       

        return True

 

Queue를 사용해도 똑같은 방법으로 풀 수 있다.

 

차이점은 FIFO를 구현하기 위해 pop(0)을 한 것 뿐이다.

# Definition for a binary tree node.

class TreeNode:

    def __init__(self, val=0, left=None, right=None):

        self.val = val

        self.left = left

        self.right = right

class Solution:

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:

       

        queue = []

        if not root:

            return False

           

        queue.append([root.left, root.right])

        while(len(queue) > 0):

            left, right = queue.pop(0)

           

            if left and right:

                if left.val != right.val: return False

                queue.append([left.left, right.right])

                queue.append([right.left, left.right])

       

            elif left or right: return False

       

        return True

 

질문이나 지적은 댓글로..