[python3] 104. Maximum Depth of Binary Tree

풀이 일자: 23.02.16

난이도: [Easy]

분류: [Tree, DFS, BFS]

문제 내용

이진 트리의 root Node가 주어지면 해당 tree의 최대 depth를 구하는 문제이다.

 

 

문제 해결 흐름

1. 단순한 트리 순회 문제로 트리 순회 알고리즘 둘 중 아무거나 사용해도 무방하다.

→ BFS를 이용해 구해보자.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:

        if not root:
            return 0;

        ans = 1;
        q = deque();
        q.appendleft([root, 1]);

        while (1):
            ele = q.pop();
            node = ele[0];
            depth = ele[1];
            if (node.left):
                q.appendleft([node.left, depth + 1]);
                ans = max(ans, depth + 1);
            if (node.right):
                q.appendleft([node.right, depth + 1]);
                ans = max(ans, depth + 1);
            if len(q) == 0:
                break;

        return ans;

Time Complexity: O(N)

시간복잡도는 Tree의 모든 노드를 순회해야하기에 Tree node의 갯수만큼 시간복잡도가 나올 것이다.

 

Space Complexity: O(2^m)

공간복잡도는 현재 DFS를 위해 queue를 사용하고 있는데 0-based depth기준으로 2의 최대 depth 승만큼의 공간복잡도를 가지면 된다고 보면 된다.

 

 

다른 해결 방식

1. BFS방식이 아닌 DFS방식으로도 해결 가능하다.

→ 좌우로 계속해서 나눠가며 Divide 하고 가장 최소 단위를 찍었을 때 다시 합해나가며 처리하는 Conquer하는 방식이다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0;

        lefttree = self.maxDepth(root.left);
        righttree = self.maxDepth(root.right);
        return max(lefttree, righttree) + 1;

=> 함수 재귀호출이 반복적으로 이루어지고 있으며 이를 위한 스택으로 인해 공간이나 시간적으로 모두 불리한 알고리즘인 것으로 보인다.

 

 

Time Complexity: O(N)

시간복잡도는 Tree의 모든 노드를 순회해야하기에 Tree node의 갯수만큼 시간복잡도가 나올 것이다.

 

Space Complexity: O(Height of tree)

함수 재귀를 위한 스택 사이즈인 Tree의 깊이만큼의 공간복잡도가 필요하다.

 

 

문제 링크

https://leetcode.com/problems/maximum-depth-of-binary-tree/

Maximum Depth of Binary Tree - LeetCode