104. Maximum Depth of Binary Tree

문제

---

설명

이진 트리의 루트를 받아 해당 트리의 가장 깊은 깊이(depth)를 반환하면 된다.

트리의 최고 깊이를 찾는 문제니까 DFS를 이용해서 문제를 풀었는데 DFS는 스택 또는 재귀함수로 구현할 수 있다.

나는 스택보단 재귀함수가 좀 더 보기 편해서 재귀함수로 구현했다.

풀이

var DFS = (node, depth) => {
    // 탐색할 노드가 없으면 lev를 반환
    if(!node) return depth;
    
    // 왼쪽, 오른쪽 순으로 순회하며 탐색
    let left = DFS(node.left, depth + 1);
    let right = DFS(node.right, depth + 1);
    
    return Math.max(left, right);
}
/**
 * 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) {
    return DFS(root, 0);
};

root node(3)에서 시작:

if(!node) return depth

1. 빈 노드가 이니기 때문에 계속 진행한다.

let left = DFS(node.left , depth + 1);

2. 왼쪽 노드(9) 호출.

child node(9) 호출:

if(!node) return depth

1. 빈 노드가 아니니까 패스

let left = DFS(node.left , depth + 1);

2. 왼쪽 노드를 호출하지만, 빈 노드여서 현재 depth인 1 반환.

let right = DFS(node.right , depth + 1);

3. 오른쪽 노드 역시 빈 노드여서 1 반환.

root node(3)으로 돌아가기:

1. 왼쪽 노드 탐색 후 오른쪽 노트 탐색

let right = DFS(node.right , depth + 1);

child node(20) 호출:

1. 빈 노드가 아니니까 패스
2. 왼쪽 노드 15 호출

child node(15) 호출:

1. 자식 노드가 없으니 depth = 2 반환.

child node(20)으로 돌아가기:

1. 오른쪽 노드 7 호출

child node(7) 호출:

1. 자식 노드가 없으니 depth = 2 반환.

child node(20)으로 돌아가기:

return Math.max(left, right);

1. 노드 20의 왼쪽 노드 13, 오른쪽 노드 7의 깊이를 비교해서 더 큰 값을 반환.

root node(3)으로 돌아가기:

let left = DFS(node.left, depth + 1);
let right = DFS(node.right, depth + 1);

return Math.max(left, right);

1. left는 1, right는 2이므로 둘 중 더 큰 수인 right = 2 를 반환.