[LeetCode] Maximum Depth of Binary Tree (재귀함수 이해하기)

문제 

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.

 

주어진 이진트리의 최대 깊이를 반환하여라. 이진트리의 최대 깊이는 루트 노드에서부터 가장 멀리 떨어진 리프 노드까지의 길이를 의미한다. 

문제 풀이 

사실 문제를 '어떻게 풀어야겠다.'하는 감이 전혀 오지 않았다. 배열의 길이를 나눠서 계산을 해야하나 싶었지만, 전혀 풀리지 않았고. '재귀함수'라는 키워드를 듣고도 선뜻 떠오르지는 않았다. 재귀함수가 자기 자신을 호출하는 함수라는 것을 알고 있을 뿐 전혀 응용하지 못하고 있다는 생각이 들어, 이참에 다시금 정리하는 시간을 가져볼까한다.  

 

재귀함수

앞서 언급했듯, 재귀함수(recursion)는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 재귀함수에는 반드지 종료조건이 필요하며, 종료조건에 도달한 함수는 실행순서의 반대로 연산을 시작한다. 재귀함수의 대표적인 예인 팩토리얼 함수를 통해 다시 이해해보면 다음과 같다. 

• 팩토리얼

function factorial(n) {
    // Base case: If n is 0 or 1, the factorial is 1.
    if (n === 0 || n === 1) {
        return 1;
    }
    
    // Recursive case: Calculate factorial by multiplying n with factorial(n-1).
    return n * factorial(n - 1);
}

양수의 팩토리얼(n!)을 구하는 함수인데, 처음 함수를 마주했을 때 든 의문은 do-while이 없는데 어떻게 함수가 호출을 시작하고 멈추는가였다. 

const result = factorial(5);
console.log(result); // Output: 120

함수 factorial(n)은 n이 0 또는 1인지 체크하면서 시작한다.

 if (n === 0 || n === 1) {
        return 1;
}

이 기본 조건에 따라 재귀함수 factorial(n)은 factorial(1) 또는 factorial(0) 일 때 1을 반환하면서 종료된다. 그 다음으로 든 질문은 n으로 주어진 5가 어떻게 4가 되고, 3이 되는가였다. 함수는  n * facotiral(n-1)을 통해 주어진 n보다 1씩 작은 값을 재귀함수로 호출하게 된다. 

 

그렇다면, 이 모든 함수의 결과가 어떻게 계산되는가. 그래서 대체 왜 factorial(5)는 결과로 120을 반환하는가. 이부분을 이해하기 위해서는 실행을 마친 재귀함수가 어떻게 연산되는지를 이해해야 했다.

factorial(5) → 5 * factorial(4)
	factorial(4) → 4 * factorial(3)
		factorial(3) → 3 * factorial(2)
			factorial(2) → 2 * factorial(1)
				factorial(1)  // 1을 반환
				2 * 1 = 2
			3 * 2 = 6
		4 * 6 = 24
5 * 24 = 120

가장 마지막에 연산된 factorial(1)은 1로. factorial(2) = 2 * 1 이 된다. 이를 역순으로 거슬러 올라가면 factorial(5)의 결과는 120이 된다. 그렇다면, 이 재귀함수를 이번 문제에 어떻게 적용해 볼 수 있을까? 

 

 

상세 풀이

주어진 root의 값이 [3, 9, 20, null, null, 15, 7]라고 하자. 

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

var maxDepth = function(root) {
    // Base case: If the tree is empty (root is null), the depth is 0.
    if (root === null) {
        return 0;
    }
    
    // Recursively calculate the maximum depth of the left and right subtrees.
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    
    // Return the maximum depth among the left and right subtrees, plus 1 for the current node.
    return Math.max(leftDepth, rightDepth) + 1;
};

 

코드가 바로 이해가 가지 않으니 주어진 root를 이진 트리로 그리보자.

     3
    / \
   9  20
      / \
     15  7

이제 주어진 배열의 숫자를 차례로 탐색할 텐데 값이 null이 되면 배열을 다 순회한 것으로 판단하고 함수를 종료하기로 한다.

const leftDepth = maxDepth(root.left);
const rightDepth = maxDepth(root.right);

배열의 가장 첫번째 값인 3에서 시작하면, leftDepth는 9, rightDepth는 20이 될것이다. 

 

이제 9를 살펴보면, 9의 leftDepth,rightDepth모두 'null'로 해당 숫자의 서브트리는 자신 1개 뿐이 된다. 따라서 최대 깊이는 1 + 0 = 1을 반환한다. 다음으로 20을 살펴보자. 

     20
    / \
   15  7

20의 maxDepth(root.left)는 15, masDepth(root.right)는 7을 반환한다.다음으로 15와 7을 순서대로 살펴보면, 9와 마찬가지로 서브 트리가 없어 각각 1 + 0 = 1을 반환하게 되며 더이상 배열 내에 체크할 숫자가 없어져 재귀함수는 종료된다.이제 나온 값을 차례로 연산하면, maxDepth는 3이 된다.