[BFS / 이진트리] LeetCode 101. Symmetric Tree

 

이진트리가 데칼코마니 같은 형식인지 확인하는 문제

 

내 첫 아이디어는 BFS로 왼쪽트리 따로 탐색(왼쪽->오른쪽방향), 오른쪽트리 따로 탐색(오른쪽->왼쪽방향)

BFS로 방향 고려해서 탐색한다는 아이디어 잘 떠올렸따.

각각 탐색한 결과를 left, right 배열에 담아서 최종적으로 left, right 배열이 같은지 다른지 확인한다.

# 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: TreeNode) -> bool:
        # 왼쪽트리의 왼쪽부터 탐색 = 오른쪽 트리의 오른쪽부터 탐색 (BFS 탐색)
        left = []
        right = []
        
        q = []
        
        # left
        if root.left is not None:
            q.append((root.left, root.left.val))

        while q:
            t,v = q.pop(0)
            left.append(v)

            if v is None:
                continue
            #if t.left is None and t.right is None : #끝점
            #    continue

            if t.left is not None:
                q.append((t.left, t.left.val))
            else:
                q.append((t.left, None))

            if t.right is not None:
                q.append((t.right, t.right.val))
            else:
                q.append((t.right, None))
                
        print(left)            
        
        
        # right
        if root.right is not None:
            q.append((root.right, root.right.val))
        while q:
            t,v = q.pop(0)
            right.append(v)
            
            if v is None:         
                continue
            #if t.left is None and t.right is None : #끝점
            #    continue
                       
            
            if t.right is not None:
                q.append((t.right, t.right.val))
            else:
                q.append((t.right, None))
                
            if t.left is not None:
                q.append((t.left, t.left.val))
            else:
                q.append((t.left, None))

                
        print(right)         
                
        if left == right: return True
        else: return False
        
        

 

시간복잡도(추측) : O(N) N개 노드 전부 탐색

공간복잡도(추측) : O(N) 탐색한 노드를 큐에도 넣고, left right 배열에도 넣는다 (O(N)+O(N))

 

근데 굳이 left, right 배열을 따로 사용할 이유가 있을까?

(근데 아래 개선한 코드랑 내가 처음 작성한 코드랑 복잡도는 큰 차이 안남)

---

 

솔루션 보고 개선한 코드. 애초에 큐에 넣을때 왼쪽트리 왼쪽 -> 오른쪽 트리 오른쪽 -> 왼쪽트리 오른쪽 -> 오른쪽트리 왼쪽 순서로 넣는다. 그러면서 왼쪽트리값, 오른쪽트리값을 각각 pop(0)으로 빼서 값을 비교하고 큐에 또 탐색할 노드 집어넣는다. 이 과정을 큐가 빌 때까지 반복한다.

맨 처음 while문에서 t1.left t2.right 와 t1.right t2.left이 큐에 들어온다.

그 다음 while문에서 t1.left t2.right가 pop되면서 3,3,4,4 노드가 들어간다.

그 다음 while문에서는 맨처음 t1.right t2.left가 pop되면서 4,4,3,3 노드가 들어간다.

아래 코드를 실행하면 중복탐색?이 발생하게 되네. 이미 큐에 넣었던 애들인데 한 번 더 넣게 되어 있다. 왜냐면 맨처음 while문에서 t1.left t2.right와 t1.right t2.left가 같은 노드이기 때문이다.

# 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: TreeNode) -> bool:
        # 왼쪽트리의 왼쪽부터 탐색 = 오른쪽 트리의 오른쪽부터 탐색 (BFS 탐색)
        
        q = []
        q.append(root)
        q.append(root)
        
        while q:
            t1 = q.pop(0)
            t2 = q.pop(0)
            
            if t1 is None and t2 is None : continue
            if t1 is None or t2 is None : return False
            if t1.val != t2.val : return False
            
            q.append(t1.left)
            q.append(t2.right)
            q.append(t1.right)
            q.append(t2.left)

        return True

시간복잡도 O(N)

공간복잡도 O(N)