[LeetCode] 111. Minimum Depth of Binary Tree (트리 깊이 구하기)

Add to ListShare

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

 

Example 1:

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

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6] Output: 5

 

트리를 순회하면서, 해당 트리의 최소 깊이를 구하면 된다.

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

const minDepth = (root) => {
    if(!root) return 0;
    const left = minDepth(root.left);
    const right = minDepth(root.right);
    
    return 1+(Math.min(left, right) || Math.max(left, right));
}

릿코드는 가끔 인수를 숫자가 아니라, 자기네들이 정한 object로 주는데, 위에 jsdoc을 제대로 읽어야 문제를 풀 수 있다.

 

핵심 아이디어

왼쪽 자식 노드가 있다면 왼쪽 노드에서의 최소 깊이를 구한다.

오른쪽 자식 노드가 있다면 오른쪽 노드에서의 최소 깊이를 구한다.

왼쪽, 오른쪽 깊이 중 가장 작은 깊이를 선택한다. 만약 왼쪽, 오른쪽 깊이 중 가장 작은 깊이가 0이라면

왼쪽, 오른쪽 깊이 중 가장 큰 값을 선택한다.

즉, 큰 문제를 작은 문제로 쪼개어서 생각해야한다.

이 문제는 나중에 다시 풀어보면서 사고하는 흐름을 훈련해야겠다.