99클럽 코테 스터디 14일차 TIL + 이진 트리, [leetcode] Maximum Depth of Binary Tree

✨ 문제 

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.

 

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

 

 

 

✨ 개념

이진 트리

- 분할 정복 탐색 알고리즘으로 빠른 속도로 탐색 가능

- 모든 노드가 2개의 서브 트리를 갖는 트리. 서브트리는 공집합일 수 있음.

- 모든 노드가 최대 2개의 자식 노드가 존재할 수 있음.

- 모든 노드의 차수가 2 이하.

- 이진 트리에는 서브 트리간 순서가 존재하며 왼쪽 트리와 오른쪽 트리가 구별됨.

 

 

 

✨ 최종코드

/**
 * 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) {
        if (root == null)
            return 0;

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return Math.max(left, right) + 1;
    }
}

 

오늘의 문제는 주어진 트리의 레벨을 구해 리턴하는 문제이다.

 

일단 root가 null인 경우 0을 리턴하도록 하였다.

left와 right라는 정수형 변수를 선언하여 left에는 재귀호출을 하며 root.left를 전달해주고, right에는 재귀호출로 root.right를 전달해준다. 왼쪽과 오른쪽 자식노드의 재귀호출이 끝나면 Math.max를 사용해 left와 right 중 더 큰 값에 +1을 하여 리턴해준다.