Maximum Depth of Binary Tree

문제

이진트리를 주고 가장 깊은 노드의 level을 구하는 문제이다.

접근

주어진 문제의 노드는 다음과 같다.
root = [3,9,20,null,null,15,7]

먼저 while문을 사용해서 깊이를 구하는 코드를 구현해 보았다

while(true) {
	if(root.left != null && root.right != null) {
     	 break
    }
  
  	if(root.left != null) {
     	left += 1
        continue
    }
  
  	if(root.right != null) {
     	left += 1
      	continue
    }
}

이와 같은 코드로 오른쪽 노드에 해당하는 깊이도 계산한다음 return으로 Math.max(left,right)를 사용해서 깊이를 구현하려고 했다.

하지만 해당 이진트리는 부모 node의 값이 null인 경우도 존재했고, 테스트 코드에서 실패하게 되었다. while문의 늪에 빠져버리게된 나는 결국 다른 사람의 코드를 참고하게 되었다.

다른 사람의 코드이다

var maxDepth = function(root) {
    if (!root) {
        return 0;
    }

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

    return Math.max(leftDepth, rightDepth) + 1; 
};

이런식으로 왼쪽, 오른쪽 노드를 각각 재귀를 통해서 깊이를 구해주면 원하는 결과값을 얻을 수 있다.

느낀점

DFS에서는 재귀를 사용해서 문제풀이가 해결되는 경우가 많다. 이전부터 재귀함수를 사용해야할 때 제대로 방향성을 잡지 못하는 경우가 많았는데, 이번 코테 연습들을 통해서 해당 부분을 훈련해야 할 것이다.