1. 오늘의 문제

Maximum Depth of Binary Tree

• 출처 : leetcode

2. 문제 분석

• root : 이진 트리의 루트 노드
• 리턴 값 : 제일 깊은 루트의 깊이
• 노드의 개수 : 0 이상 $10^4$ 이하
• 노드의 값 : -100 이상 100 이하
  
  
• Example 1:
  • Input: root = [3, 9, 20, null, null, 15, 7]
  • Output: 3
• Example 2:
  • Input: root = [1, null, 2]
  • Output: 2

3. 문제 풀이

1. 우선 이진트리를 순회해야 하기 때문에 재귀 호출 활용
2. root부터 시작해서 왼쪽, 오른쪽 서브 트리 계속 돌아야 함
3. 돌 때마다 카운트 하면 될까?
4. Math.max 메소드 활용하면 될 듯 : Math.max(왼쪽 깊이, 오른쪽 깊이)

4. 구현 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        // null일때의 조건
        if(root == null) {
            return 0;
        }

        // 왼쪽 부분 트리에 대한 재귀 호출로 깊이 탐색
        int leftDepth = maxDepth(root.left);

        // 오른쪽 부분 트리에 대한 재귀 호출로 깊이 탐색
        int rightDepth = maxDepth(root.right);

        // 최종 리턴 : 왼쪽, 오른쪽 서브 트리의 깊이 중 가장 큰 값
        // root is not null 이면 root 깊이 1까지 포함해 리턴
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

5. 오늘의 회고

• 이진 트리에 대해 많이 문제를 풀다 보니 생각보다 어렵진 않았다. 근데 구현 조건을 어떻게 해야할지 모르겠어서 일단 이진트리를 직접 풀어봤다.
  
• 그림판으로 직접 풀어보니 좀 더 쉽게 이해되고 그것에 맞춰 로직을 짜고 구현할 수 있었다.
  
• 꾸준한 공부는 발전이 된다!

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL