[dfs] 104번 이진트리 최대 깊이

문제

이진 트리의 루트가 지정되면 최대 깊이를 반환합니다.

이진 트리의 최대 깊이는 루트 노드에서 가장 먼 리프 노드까지 가장 긴 경로를 따라 이어지는 노드 수입니다.

예시

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: 3

Example 2:

Input: root = [1,null,2]
Output: 2

Example 3:

Input: root = []
Output: 0

Example 4:

Input: root = [0]
Output: 1

제약

• 트리의 노드 수는[0, 10^4] 범위에 있습니다.
• -100 < = Node.val < = 100

코드1

const dfs = (node, depth) => {
  if (!node) {
    return depth
  }
  return Math.max(dfs(node.left, depth + 1), dfs(node.right, depth + 1))
}

const maxDepth = root => {
  return dfs(root, 0);
}

풀이1

트리의 최대 깊이를 측정하는 문제이므로 dfs로 문제를 풀었다. 그중 재귀 방식으로 구현을 선택했다.

재귀를 통해서 최종적으로 리프노드까지 탐색을 하고 그동안 얼만큼의 깊이로 재귀가 되었는지 알기위해 인자로 depth를 주었다.

depth는 한번 재귀를 탈때마다 하나 아래의 자식노드로 이동하는 것이기 때문에 1씩 더해주면서 재귀를 진행한다.

왼쪽 자식과 오른쪽 자식으로 뻣어나가면서 재귀를 진행한다.

재귀 종료조건으로 마지막 노드에 도달했을 때는 그동안 축정해온 depth를 리턴받는다.

그리고 리턴받은 왼쪽 자식과, 오른쪽 자식의 depth중 큰것을 리턴 한다.

코드2

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

풀이2

코드1에서는 재귀가 진행될수록 depth를 더해갔지만 이 코드는 반환값을 1씩 더하면서 올려주는 형태이다.

즉 최종 리프노드에서 0을 반환 받고 그 부모에서 1을 더하고 다시 그 부모에서 1씩 더해서 위로 올라가는 형태이다.