[Easy] 104. 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.

이진 root트리의 최대 깊이를 반환합니다 .

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

 

예시

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

 

해결 과정

lev 변수를 활용하여 재귀로 문제를 푸려고 시도하였다. 

하지만 이상하게 재귀 함수에서 반환이 제대로 이루어지지 않았다.

디버깅을 통하여 코드 안에서 어떻게 돌아가는지 확인을 하고 싶었으나, 트리 문제였기 때문에 Test Case를 내가 직접 만들어 넣는 게 어려웠다.

if(!node)를 한 번 확인하고, 또 한 번 node.left와 node.right가 있는지 조건문을 달았었는데, 조건문을 삭제하니 문제가 해결되었다. 또한, left, right의 값 중 큰 값을 반환하게 하였다.

 

다른 분들의 코드를 보니 훨씬 더 간단하게 해결할 수 있었다.

참고용으로 따로 올려놓도록 하겠다

 

• 재귀를 돌 dfs 함수를 만든다. 매개변수는 node와 node의 lev(레벨)을 받는다.
  • 만약 node가 undefined이거나 null이면 현재 node의 lev을 반환한다.
  • left와 right를 dfs 해준다. 이 때 lev를 하나 증가시킨다. (아래 노드로 내려가는 것이기 때문)
  • 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) {
    
    const dfs = (node, lev) => {
        if(!node) return lev;        
        
        let left = dfs(node.left, lev + 1);
        let right = dfs(node.right, lev + 1);
        
        return Math.max(left, right);
    }
    
    return dfs(root, 0);
};

 

더 간단하게 푸는 방식

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