[알고리즘] #Minimum Depth of Binary Tree

출처: https://leetcode.com/problems/minimum-depth-of-binary-tree/

Minimum Depth of Binary Tree - LeetCode

 

문제

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:

Given binary tree [3,9,20,null,null,15,7],

 

 

---

풀이

이 문제는 지난 번에 풀었던 Maximum depth of binary tree 문제와 똑같이 풀면 되겠다~ 라고 생각했는데 한 가지 걸림돌이 있었다.

바로 가장 작은 높이 값을 구하는 부분이었는데, 최대값이야 순회하면서 높이 비교해서 가장 큰 값을 마지막에 리턴해주면 됐었다.

하지만 가장 작은 높이 값은 최대값보다 좀 더 생각을 많이 해야 했다.

 

먼저, root 노드 자체가 null 또는 undefined인 경우에는 높이가 0이다.

root 노드의 왼쪽, 오른쪽 자식 노드가 모두 없는 경우에는 높이가 1이다.

그래서 이 부분은 먼저 조건문으로 걸어놨다.

 

그리고 한 쪽만 자식노드가 없는 경우, 다른 쪽 자식 노드를 순회하면서 높이 값을 구한다.

둘다 자식노드가 있는 경우에는 왼쪽과 오른쪽의 높이를 비교해서 최솟값을 리턴한다.

 

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    // root 노드 자체가 null이면 높이=0
    if(!root) {
        return 0;
    }
    
    // root 노드의 자식 노드가 없는 경우 높이=1
    if(!root.left && !root.right) {
        return 1;
    }
    
    // 자식노드의 높이에 1을 더한다.(현재 루트노드의 높이 = 1)
    var leftDepth = minDepth(root.left) + 1;
    var rightDepth = minDepth(root.right) + 1;
    
    // 왼쪽 자식 노드가 없는 경우, 오른쪽 자식 노드를 루트노드로 하는 노드의 높이를 구한다.
    if(!root.left) {
        return rightDepth;
    }
    // 오른쪽 자식 노드가 없는 경우, 왼쪽 자식 노드를 루트노드로 하는 노드의 높이를 구한다.
    if(!root.right) {
        return leftDepth;
    }
           
    // 왼쪽과 오른쪽 자식노드 중 높이가 작은 값을 구한다.
    return Math.min(leftDepth, rightDepth);
    
};

 

 

참고: https://gogomalibu.tistory.com/47

[알고리즘] #Maximum Depth of Binary Tree