[LeetCode 104] Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Maximum Depth of Binary Tree - LeetCode

 

Think

책대로 스택을 사용하는 BFS 반복구조로 풀이해보자!

 

파이썬의 큐 자료형보다는 데크를 쓰는 게 성능이 좋다.

 

 

Solution

# 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 maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        
        depth = 0
        queue = collections.deque([root]) #큐
        
        while queue : #큐가 비어있지 않으면
            depth += 1
            #현재 큐에 담긴 원소개수만큼만 반복
            #(이번에 추가되는 자식노드들이 나타나기 직전에 반복문을 탈출함)
            for _ in range(len(queue)) : 
                cur_root = queue.popleft() #큐에서 하나를 꺼내어 현재 노드로 사용
                
                #현재노드의 자식노드 확인 및 추가
                if cur_root.left : #왼쪽 자식노드가 존재하면
                    queue.append(cur_root.left) #큐에 추가
                if cur_root.right : #오른쪽 자식노드가 존재하면
                    queue.append(cur_root.right) #큐에 추가
                    
            #for문을 탈출했다 = 이번 depth의 모든 노드를 탐색했다!
            #다음while문 실행 시 depth + 1 됨!
            
        return depth

 

 

 

Get

BFS 연습하자,,