Problem Solving/LeetCode
Leetcode 104. Maximum Depth of Binary Tree
yuseon-Lim
2021. 2. 8. 11:20
Leetcode 104. Maximum Depth of Binary Tree
https://leetcode.com/problems/maximum-depth-of-binary-tree/
Maximum Depth of Binary Tree - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
Logic
처음엔 보통 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
파이썬 알고리즘 인터뷰
코딩 테스트와 인터뷰를 준비하는 취준생과 이직자를 위한 알고리즘 문제 풀이 완벽 마스터!세계 최고 온라인 문제 풀이 사이트인 리트코드(LeetCode)의 기출문제 풀이와 분석!『파이썬 알고리즘
www.yes24.com
반응형