[LeetCode] Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

 

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

---

 

이진 트리의 깊이? 길이를 구하는 문제.

 

depth가 2 = 주어진 배열의 길이가 1 + 2
depth가 3 = 주어진 배열의 길이가 1 + 2 + 2*2 + 2*2*2...
결국 depth만큼 1 + 2 + 2*2 + 2*2*2 + 2*...가 되는거니까, 전체 배열의 길이를 구하면 그냥 규칙상 depth를 알 수 있다.
근데 모든 노드가 끝까지 차 있어야 가능하기도 하고, 애초에 그런 식으로 풀라고 만든 문제가 아니다.

 

/**
 * 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 maxDepth = function(root) {
    if(!root){
        return 0;
    }
    let depth = 0;
    let res = 1;
    const check = (val, text) => {
        if(val.right && val.left){
            depth--;
        }
        if(val.right){
            depth++;
            check(val.right);
        }
        if(val.left){
            depth++;
            check(val.left);
        }
    }
    check(root);
    let num = 1;
    while(depth > 0){
        depth -= num;
        num = num * 2;
        res ++;
    }
    return res;
};

 

그래도 해봄ㅋㅋ

왼쪽 또는 오른쪽이 있는 경우 깊이를 +1 하고, 둘 다 있으면 -1 해 준다.

결국 전체 배열 길이를 구하고 규칙으로 구해내는 거나 다름이 없음.

 

그냥 이게 될까? 확인해 보고 싶었는데 아니나 다를까 안된다.

계속 한 쪽으로만 노드가 있는 편향트리의 경우를 커버하지 못했음.

 

 

이런 거.

 

var maxDepth = function(root) {
    if(!root){
        return 0;
    }
    let res = 1;
    const check = (val, depth) => {
        const left = val.left;
        const right = val.right;
        if (!val.left && !val.right) {
            res = Math.max(res, depth);
        }
        if(left){
            check(left, depth + 1);
        }
        if(right){
            check(right, depth + 1);
        }
    }
    
    check(root, res)
    return res;
};

 

재귀함수를 아까보단 좀 더 활용해서 푼 게 이것...

한 쪽 끝까지 탐색하는 걸 반복한 다음 가장 큰 걸 리턴하는 방식이다.

 

이런 걸 DFS(Depth First Search, 깊이 우선 탐색)이라고 한다는군.

트리나 그래프를 탐색하는 기법 중에 하나로,

시작 노드에서 자식 노드를 순서대로 탐색하되 깊이 우선으로 진행하는 알고리즘이다.

일반적으로 스택을 이용한 반복문이나 재귀함수로 구현할 수 있다.

 

왔다갔다 하지 않고, 각 분기별로 끝까지, 제일 깊은 곳까지 탐색한다는 특징이 있다.

더 자세한 내용은 여기서 > https://olrlobt.tistory.com/35

 

어렵다...

 

1등 코드는 이렇게 돼 있음. (주석 추가)

var maxDepth = function(root) {
    if (!root) {
        return 0;  // 트리가 비어있으면 깊이는 0임
    }
    
    // 왼쪽과 오른쪽 트리의 최대 깊이를 구하고 더 큰 값을 고름
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    // 두 트리 중 더 큰 깊이값에 1을 더하고 리턴
    return Math.max(leftDepth, rightDepth) + 1;
};

깔끔하구만...

 

 

ㄹㅇㅋㅋ 재귀함수 어떻게 쓰는 건지 알고 있다고 생각했는데 이게 또 이렇게 되네...