리트코드 - 104. Maximum Depth of Binary Tree

리트코드 - 104. Maximum Depth of Binary Tree

출처 - https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

이진 트리의 root가 주어지면 최대 깊이를 반환합니다.
이진 트리의 최대 깊이는 root 노드에서 가장 먼 leaf 노드까지 가장 긴 경로를 따라 있는 노드 수입니다.

 

의사코드

함수 maxDepth        if (root == null)         return 0     Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 리턴 함수끝

 

풀이코드

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;    
        }
        
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

코드설명

재귀방식을 이용한 depth 탐색 방법이다.

노드의 자식노드들이 누적된 depth를 가지게 재귀를 구현하면 된다.

 

제일 하위 노드는 자식이 없으므로 null일테고, 이때는 0을 리턴해야 한다.

그리고 각 노드는 왼쪽 오른쪽 노드 두 개의 자식노드가 있으므로 두 노드값을 비교해서 큰 값을 찾아 +1 해주면 된다.

이렇게 하면 각 노드는 자기 자신을 포함한 Depth의 최대값을 가지게 되고, root까지 올라가게 되면 최대 depth값이 나오게 된다.

 

시간복잡도 - O(n) (n은 node수)

공간복잡도 - O(log n ~ n) (균형이진트리라면 log n, 최악의 경우는 n)

 

문제를 풀며 생각한 흐름과 배운 점

문제를 쪼개서 생각하니 생각보다 답이 쉽게 나왔다.

다른 사람들의 풀이를 봤는데 비슷한 것 같다. 메모리를 줄여보려고 다른 코드들 해봤는데 큰 차이가 없었다.

그냥 그때그때 리트코드 채점 컴퓨터 메모리에 따라서 조금 낮게 나오고 크게 나오고 하는듯 하다.

 

정리

이진트리에서 MaxDepth를 찾는 간단한 방법.