[LeetCode] 104. Maximum Depth of Binary Tree

 문제

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

주어진 이진트리의 최대 깊이를 찾는 문제

 

 

 

 

레벨 오더는 BFS와 유사한 방식으로 구현이 됨.

일단 queue로 시작하여 첫번째 root 노드에 대해 큐에 인큐를 함(이 노드에 곧 방문할 예정이라는 의미)

 

왼쪽 오른쪽에 있는 하위(child) 노드들에 대해 level by level로 방문

depth가 몇인지를 기록해야함 -> 노드들 저장할 때 노드의 값 뿐만 아니라 노드가 depth가 몇인지도 같이 저장해야 함

 

큐의 가장 앞에 있는 노드를 디큐에서 그 곳에 방문 (해당 노드의 차일드 노드들을 방문 예약 걸어둠)

가장 마지막에 방문하는 노드의 depth가 Max depth가 됨.

노드의 갯수만큼 코드 실행하게 됨 => O(N)의 시간복잡도를 가짐.

 

제약조건

• 1 < n < 10^4  => 설명: O(N^2)가 아닌 O(N)의 시간복잡도를 가지므로 시간초과가 일어날 일 없음.
• -100 <= Node.val <= 100

 

 

코드 설계 & 구현

from collections import deque

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        max_depth = 0
        if root is None:
            return max_depth
        q = deque()
        q.append((root, 1))

        while q:
            cur_node, cur_depth = q.popleft()
            max_depth = max(max_depth, cur_depth)
            if cur_node.left:
                q.append((cur_node.left, cur_depth + 1))
            if cur_node.right:
                q.append((cur_node.right, cur_depth + 1))
        return max_depth


# 트리구현(Input 값 세팅)
class TreeNode:
    def __init__(self, l = None, r = None, v = None): # 값이 안주어지면 None
        self.left = l
        self.right = r
        self.value = v

root = TreeNode(v=3)
root.left = TreeNode(v=9)
root.right = TreeNode(v=20)
root.right.left = TreeNode(v=15)
root.right.right = TreeNode(v=7)


print(maxDepth(root))

 

 

PostOrder(후위순회) 풀이

 

rom collections import deque

def maxDepth(root):
    if root is None:
        return 0;
    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)
    print(left_depth, right_depth)
    return max(left_depth, right_depth) + 1

 

 

 

 

 

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

Maximum Depth of Binary Tree - LeetCode