104. Maximum Depth of Binary Tree

BFS로 구해서 층 하나 내려갈 때마다 깊이에 +1 해주면됨

# 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 maxDepth(self, root):

        if not root:
            return 0
            
        queue = [root]
        depth = 0

        while queue:
            # 층 하나 내려 갈때마다 깊이 +1 해줌
            depth += 1

            for _ in range(len(queue)):
                cur_root = queue.pop(0)

                if cur_root.left:
                    queue.append(cur_root.left)
                if cur_root.right:
                    queue.append(cur_root.right)

        return depth

큐를 그냥 리스트로 해도되는데 리스트의 pop(0)이 O(n)이기 때문에 deque를 사용하면 pop(0)이 O(1)이니 deque 사용하는게 더 좋음.

import collections


class Solution:
    def maxDepth(self, root):

        if not root:
            return 0

        queue = collections.deque([root])
        depth = 0

        while queue:
            # 층 하나 내려 갈때마다 깊이 +1 해줌
            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)

        return depth

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