Leetcode Python - 110. Balanced Binary Tree

Leetcode #110 - Balanced Binary Tree

이제 두 번째로 100 문제들을 풀어보겠습니다. 리트코드의 문제 110 ‘Balanced Binary Tree’을 파이썬으로 풀어 보도록 하겠습니다.

discuss 참고 포인트는 이진트리에서 postorder traversal을 이용하는 것입니다.

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

class Solution(object):
    def isBalanced(self, root):
            
        def check(root):
            if root is None:
                return 0
            left  = check(root.left)
            right = check(root.right)
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return 1 + max(left, right)
            
        return check(root) != -1

시간복잡도는

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

공간복잡도는

• O(v) : v(이진트리의 높이) 최악의 경우 O(n) : 비대칭 이진트리 케이스