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.
Constraints: 1. The number of nodes in the tree is in the range[0, 104]. 2. -100 <= Node.val <= 100
# 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
from collections import deque
class Solution:
def maxDepth(self, root: TreeNode) -> int:
level = 0
if not root:
return 0
q = deque([root])
while q:
level += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return level
이번 문제는 트리의 최대 깊이를 찾는 문제로 BST를 활용해야 했다. 처음엔 모든 노드를 훑으면서 같은 층(깊이)에 있는 노드가 아니라면 level이란 변수에 1을 더하는 식으로 했다.
같은 층에 있는 노드에 대해선 1) queue에 자식노드를 추가하고, 2) 이 자식노드들의 자식노드들이 추가될 때까지 for문을 돌렸다. for문을 빠져나올 때(=다음 층의 노드들의 차례가 왔을 때) 비로소 level += 1을 해주었다.
모든 노드에 대해서 queue에 넣고 빼고 하는 작업이 꼭 필요할까 의문을 품으며 다른 사람들의 코드를 함께 살펴봤다. 아래는 재귀구조를 통해 문제를 해결한 매우 깔끔한 코드이다.
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
left_level = self.maxDepth(root.left) + 1
right_level = self.maxDepth(root.right) + 1
return max(left_level, right_level)
맨 아래노드(=leaf node)까지 내려간 뒤에 하나씩 올라오며 깊이를 세는 로직이다. 자식노드가 없는 리프노드까지 내려가면 자식노드를 파라미터로 전달할 때 0을 리턴하고, 해당 리프노드의 리턴값은 1이 된다.
리프노드가 최대 2개(문제 제목이 Binary Tree)이므로 왼쪽/오른쪽으로 나누어서 깊이를 계산하고 최댓값을 선정하여 리턴하면 최종적으로 최대 깊이가 나오게 된다.
테스트 결과 재귀구조를 사용한 코드가 queue를 통한 반복문보다 성능이 조금 떨어지는 것으로 보였다. 그럼에도 코드의 간결함은 재귀구조가 압승인 것 같다...
