Open seungriyou opened 8 months ago
https://leetcode.com/problems/maximum-depth-of-binary-tree/
트리의 최대 깊이를 구하는 문제로, iterative(BFS)한 방법과 recursive한 방법으로 풀 수 있다.
BFS를 통해 각 레벨 단위로 방문하며 depth를 늘려나간다.
depth
이때, root가 none 값이 들어올 때에 주의한다.
root
none
레벨 단위로 방문하기 때문에 deque를 사용할 필요까지는 없다!
deque
어떤 node에 대해, 다음의 값이 해당 node를 root로 하는 트리의 최대 깊이가 된다.
node
max(left subtree의 max depth, right subtree의 max depth) + 1
이때, base condition에 주의한다!
[!important] 트리 문제는 recursion을 적용하기 쉽다!
O(n)
n/2
O(height)
height
logn
n
Approach
트리의 최대 깊이를 구하는 문제로, iterative(BFS)한 방법과 recursive한 방법으로 풀 수 있다.
Iterative (BFS)
BFS를 통해 각 레벨 단위로 방문하며
depth를 늘려나간다.이때,
root가none값이 들어올 때에 주의한다.레벨 단위로 방문하기 때문에
deque를 사용할 필요까지는 없다!Recursive 💡
어떤
node에 대해, 다음의 값이 해당node를root로 하는 트리의 최대 깊이가 된다.이때, base condition에 주의한다!
Complexity
O(n)(모든 node가 방문되어야 함)O(n)(맨 밑 level의 node 개수 -> worst case는 balanced tree 일때이므로n/2개가 될 것!) (ref)O(height)(recursion stack) (balanced tree라면height~=logn, skewed tree라면height~=n)