[HackerRank] Tree: Height of a Binary Tree (Python)

1.  문제

https://www.hackerrank.com/challenges/tree-height-of-a-binary-tree/problem

 

2. 풀이

Binary의 가장 높은 height를 구하는 문제.

현재 root node 가 None이면 -1 반환

재귀함수를 이용해서 왼쪽노드와 오른쪽 노드의 height 구한다.

 

시간 복잡도 : O(N) - 모든 노드를 한번씩 방문하므로 시간 복잡도는 N, N은 여기서 노드 수

공간 복잡도 : O(H) - 재귀호출 스택의 공간 복잡도는 트리의 높이 H 와 동일

 

3. 코드

def height(root):
    if root is None:
        return -1
    depth_left = height(root.left)
    depth_right = height(root.right)

    
    return max(depth_left, depth_right) + 1