LeetCode 111 - Minimum Depth of Binary Tree ( JavaScript )

 

안녕하세요 besforyou입니다.

 

이번 글은 리트코드 111번 문제입니다.

 

---

문제 설명

 

이진 트리가 주어졌을 때 최소 깊이를 구하라.

 

최소 깊이는 루트 노드로부터 가장 가까운 leaf 노드까지 갈 때 거쳐가는 노드의 개수입니다.

 

---

문제 풀이

깊이 우선 탐색(DFS)법으로 탐색하되 leaf 노드를 만나면 전역 변수로 선언해 높은 변수와 현재 깊이를 비교하여 현재 깊이 값이 더 작다면 변수를 교환합니다.

 

---

코드

var minDepth = function(root) {
    
    let min = 100001;
    let dfs = function(root, depth) {
        if(!root) 
            return;
        if(!root.left && !root.right) 
            if ( min > depth ) 
                min = depth;
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
    
    if ( root == null )
        return 0;
    
    dfs(root,1);
    return min;
};