[ Tree ] 104. Maximum Depth of Binary Tree (JAVA)

 

 

 

104번 문제
https://leetcode.com/problems/maximum-depth-of-binary-tree/

Maximum Depth of Binary Tree - LeetCode

 

1. 문제

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.
최대 깊이란 뿌리 노드에서 가장 먼 노드로 쭉 따라 내려갈 때 가장 긴 길이를 말한다.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 100 <= Node.val <= 100

 

 

 

2. 풀이

• runtime : 0ms
• beats : 100%
• memory : 41.8MB
• beats : 72.61%

/**
 * 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 leftDepth = 1;
        int rightDepth = 1;
        if(root.left != null){
            leftDepth += maxDepth(root.left);
        }

        if(root.right != null){
            rightDepth += maxDepth(root.right);
        }

	// 왼쪽, 오른쪽 중 숫자가 더 많은 쪽이 더 깊은 쪽이므로 큰 쪽을 반환
        return leftDepth > rightDepth ? leftDepth : rightDepth;
    }
}

→ root가 null인 경우는 depth란게 없으니 0을 바로 반환하며 끝내기
→ root의 각 자식들을 타고 내려가기 위해 왼쪽/오른쪽 깊이를 담을 변수 생성하고 root가 null이 아니기 때문에 depth 1씩 일단 갖고 시작
→ 자식이 null이 아닐 때까지 자식 node로 쭈우우욱 타고 내려가며 1씩 반환
→ 마지막에 leftDepth와 rightDepth 중 더 숫자가 큰 쪽이 더 깊고 멀기 때문에 해당 값을 반환

 

이렇게 풀었을 때 런타임은 0ms이었지만 메모리 관리는 적당하지 않았고
코드 자체도 조금 함무라비법전 같은 식이어서 맘에 들지 않았다
그래서 스터디원이 푼 코드를 봤는데 Math 클래스를 활용하여 훨씬 간단하게 풀이하였다.

 

 

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

→ 이렇게 Math 클래스의 max() 함수를 활용하여 두 값을 비교하여 바로 반환하는 한 줄로 끝낼 수 있다.

 

나도 이렇게 코드를 정리할 수 있는 능력을 길러보자!
화이팅!!!!