99클럽 코테 스터디 10일차 TIL Maximum Depth of Binary Tree

Maximum Depth of Binary Tree

• 문제 풀이

  1. 가장 긴 노드의 카운트를 구하는 문제이다.
  2. 재귀함수를 통해 각 노드 자식이 존재하다면 +1씩 더한다.
  3. null이 나올때 까지의 경우의 수에 대해 왼쪽과 오른쪽 노드에 대한 return값중 더 큰 값을 반환한다.

• 풀이 소스

/**
 * 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 {
    int left =0;
    int right = 0;
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        left = maxDepth(root.left) + 1;
        right = maxDepth(root.right) + 1;
        return left < right ? right : left;
    }
}

• 클린 소스

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return  Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }    
}

• 오늘의 회고

  • 문제 시도 및 해결

    • 최대값에 대해 재귀함수를 돌릴려는 중 count를 올리는 방법에 대해 생각했다.
    • 노드의 왼쪽과 오른쪽으로 돌렸을때 각각에 +1를하여 null을 만날때까지 재귀함수를 돌린다.
    • 그 후 둘 중 큰값을 반환하면 되는 문제였다.
    • maxDepth(root.right) + 1의 재귀는 노드가 3개일때
      1번 호출 : maxDepth(root.right) + 1
      2번 호출 : maxDepth(root.right) +1 + 1
      3번 호출 : 0 +1 +1 + 1 이 된다.
    • 해당 재귀를 왼쪽도 돌려 둘 중 큰수에 대해 return 하여 해결

  • 학습 내용 및 회고

    • 각 노드에 대해 count하는 과정에서 재귀함수를 한번 더 학습할 수 있었다.
    • 재귀를 통해 모든 경우의 수를 판단하는 그림을 그려보니 이해하는데 도움이 되었다.
    • 최근 트리 노드에 대해 재귀를 통해 문제를 풀어봐서 해결 할 수 있었지 다른 유형의 문제를 풀었다면 많은 시간을 투자했을 것 같다.
    • 문제를 많이 풀어봐야겠다.

• 다음 배울것

  • 스프링 validation 공부
  • 코테 문제 풀이