Maximum Depth of Binary Tree

---

💬 문제

[문제 링크]

이진 트리의 시작점 노드 root
이 트리의 최대 깊이가 몇 인지 반환

✍️ 나의 풀이

/**
 * 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 checkDepth = function(node, cnt) {
    let left = cnt;
    let right = cnt;
    if (node.left)
        left = checkDepth(node.left, cnt + 1);
    if (node.right)
        right = checkDepth(node.right, cnt + 1);
    return Math.max(left, right);
}

var maxDepth = function(root) {
    if (root === null)
        return 0;
    return checkDepth(root, 1);
};

재귀 함수 checkDepth 생성
왼쪽이 있으면 왼쪽으로 쭉 호출하고
더 이상 왼쪽이 없을 때 바로 이전 노드의 오른쪽을 탐색
한 층씩 위로 올라가면서 오른쪽을 쭉 탐색하는 것
양쪽을 다 확인한 노드는 왼쪽과 오른쪽 깊이 중 더 큰 값을 반환
checkDepth에 root를 넣은 결과를 반환하면 끝

📌 결과

Accepted
Runtime 56ms (Beats 50.91%)
Memory 51.51MB (Beats 44.56%)

📚 러닝 포인트

이미 한 번 이전에 풀어본 적이 있는 문제였다. 코테 연습할 때 풀어봤던 것 같다. 근데 내가 뭐라고 작성했는지 생각이 안나서 그냥 처음부터 다시 작성했다. 재귀함수는 아직도 헷갈리고 어려운 상태라 이게 맞는건가 의심하면서 일단 쓰고 제출했는데 한 번에 성공해서 신기했다. 조금 감을 잡기 시작한건가? 엄청엄청 쉬운 문제지만 그래도 기분 좋게 트리 문제를 시작하게 되었다. 앞으로 탐색 알고리즘의 파티겠지... 이번 문제는 최대 깊이를 구하는 거다 보니 DFS를 사용했다. 하지만 모든 노드를 방문해야 하는 것이므로 BFS를 사용해서 풀 수도 있다. queue를 사용해서 간단히 풀어보았다. 결과는 57ms / 51.02MB로, DFS와 크게 차이나지 않았다.

var maxDepth = function(node, cnt) {
    let queue = [node];
    let depth = 0;

    while (queue[0]) {
        let nodeCnt = queue.length;
        for (let i = 0; i < nodeCnt; i++) {
            let node = queue.shift();
            if (node.left)
                queue.push(node.left);
            if (node.right)
                queue.push(node.right);
        }
        depth++;
    }

    return depth;
}

+) 이전에 TIL로 BFS, DFS 작성한 걸 다시 보다가 이 문제를 예제로 활용했던걸 발견했다. 근데... DFS 코드가 이번에 작성한 것 보다 훨씬 간단했어... 이 바보...

var maxDepth = function(root) {
    if (!root)
        return 0;
    let leftDepth = maxDepth(root.left);
    let rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
};