LeetCode 104(Maximum Depth of Binary Tree, Python)

1. 문제 링크

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

Number of 1 Bits - LeetCode

2. 문제 설명

• 이진 트리 root가 주어졌을 때, 최대 깊이 (maximum depth)를 int로 반환
  • 여기서 최대 깊이란, 루트 노드에서 leaf 노드로 갈 수 있는 가장 긴 path에서의 노드 개수를 의미
• 예시) 아래 트리는 3-20-7 또는 3-20-15가 가장 멀리 갈 수 있는 path이고, 이는 node 3개를 거치므로 3을 반환
  •     3
       / \
      9  20
           /  \
         15   7

3. 처음 풀이

• 여기서도 재귀로 풀기!
  • 우선 root노드와 바로 아래 node들만 생각해봤을 때,
    • root노드가 none이면 path는 1이다 (root노드만 카운드) 
    • 만약 root노드가 none이 아니라면? → 여기서 재귀가 쓰인다
      • root노드가 none이 아니라면 root노드의 왼쪽 노드에서의 maxDepth, root노드의 오른쪽 노드에서의 maxDepth의 max를 비교하는 재귀를 쓴다.
        • 그러면 반복적으로 none이 아닌이상 1이 계속 더해지는 구조

# 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: Optional[TreeNode]) -> int:
        result = 1
        if root is None:
            return 0 
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

• runtime beats 96%로 일반적으로 푸는 풀이로 해결!

4. 다른 풀이

• 위의 풀이가 정석인지, 대부분이 해당 풀이의 큰 틀에서 벗어나있진 않았다. 
  
  • 아래 풀이는 return 딱 한 줄로 처리한 코드. root 가 None이면 0 반환하는 걸 한줄에 작성
  • 뭐가 더 좋은 코드인진 모르겠다 :) 

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return (max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1) if root else 0

5. 배운 점

• 재귀가 익숙해지고 있다. 
• 최대한 전체 트리로 보려하지 말고, root, root.left, root.right만 살펴보면서 재귀 규칙을 찾기!