[Leetcode/JS] 111. Minimum Depth of Binary Tree

 

문제링크 

111. Minimum Depth of Binary Tree

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

Minimum Depth of Binary Tree - LeetCode

 

 

 

 

기억하면 좋을 것 

DFS : 모든 경우를 탐색해야 할 때. 스택 , 큐, 재귀 방법

BFS: 최단 거리를 구할 때. 큐 & 반복문 방법

 

늘 재귀 종료 조건과 어떻게 반복이 되면 좋을지를 잘 생각하자.

소감

문제가 DFS로 분류 돼 있어서 재귀로 풀었다.

근데 다른 풀이 보니까 BFS로 많이풀더라...

프로그래머스 3단계가 안 풀려서 leetcode로 넘어왔다. 여기서 easy를 많이 풀고 프로그래머스 3단계나 leetcode medium으로 넘어가면 좋을 듯 하다.

 

해결 코드

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
  var checkLeafNode = function(node, depth) {
        if(!node) return 0;
        else if(!node.left && !node.right) return depth;
        else if(!node.left) return checkLeafNode(node.right, depth+1);
        else if(!node.right) return checkLeafNode(node.left, depth+1);
        return Math.min(checkLeafNode(node.left, depth+1), checkLeafNode(node.right, depth+1));
    }

var minDepth = function(root) {
    return checkLeafNode(root, 1);
};

 

 

node.left 혹은 right가 null 일때 어떻게 해 줘야할지를 고민 했는데

left 가 null 일때는 right 쪽을 return 하게 하고 right가 null일때는 left를 return 하게 했다.

 

근데 다른 사람 풀이를 보니까

 

var minDepth = function(root) {
    if (root === null) return 0
    let left = minDepth(root.left)
    let right = minDepth(root.right)
    if (root.left && root.right) return Math.min(left + 1, right + 1)
    return Math.max(left + 1, right + 1)
};

 

이렇게 푼 것도 있다. 

left right한쪽만 null일때는 큰 쪽을 return 하게 해줬다 .. 그리고 depth를 leaf node에 도달했을때도 node.left, node.right를 진행해서 0을 return해 돌아오게 만들고 left + 1, right + 1 이런식으로 끝 노드부터 +1 해주는 방법 엄청 똑똑하게 잘 생각한듯 !!!

Submission Detail