Leetcode Python - 104. Maximum Depth of Binary Tree

Leetcode #104 - Maximum Depth of Binary Tree

이제 blind 75 leetcode를 풀어보겠습니다. https://leetcode.com/discuss/interview-question/460599/Blind-75-LeetCode-Questions

리트코드의 문제 104 ‘Maximum Depth of Binary Tree’을 파이썬으로 풀어 보도록 하겠습니다.

포인트는 post-order로 traversal 하면서 depth로 1씩 더해주는 것입니다.

전체 코드는 아래와 같습니다.

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        def check(root):
            if not root:
                return 0
            
            left = check(root.left)
            right = check(root.right)
            
            return 1 + max(left, right)
        
        return check(root)

시간복잡도는

• O(n) : 모든 노드 한번씩 방문

공간복잡도는

• O(h) : h는 깊이