Leetcode 104. Maximum Depth of Binary Tree

Leetcode 104. Maximum Depth of Binary Tree

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

Maximum Depth of Binary Tree - LeetCode

Logic

• BFS구현(Python)

처음엔 보통 bfs 처럼 while문을 돌고 depth를 하나씩 늘려줬는데

while queue:
            depth += 1
            cur = queue.popleft()
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)

이렇게 하면 depth가 노드갯수만큼 증가하게 된다.(당연하지만.)

따라서 원래의 while문 아래에 for문을 추가해 새로운 레벨로 들어갔을때만 depth가 증가하게 해준다.

 

Solution

import collections

# 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: TreeNode) -> int:
        # 예외 처리
        if root is None:
            return 0

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

        while queue:
            depth += 1
            for _ in range(len(queue)):
                cur = queue.popleft()
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)

        return depth

Reference

파이썬 알고리즘 인터뷰 p.387

파이썬 알고리즘 인터뷰