문제

나만의 솔루션

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

        ldepth = self.maxDepth(root.left)
        rdepth = self.maxDepth(root.right)
        
        if abs(ldepth - rdepth) <= 1:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
        return False

왜 이렇게 풀었는지 설명해보겠다.
이 비루한 코드는 두가지 아이디어에서 출발했다.

1. 일단 최대 깊이를 구해야한다. 그래서 maxDepth를 썼다.
2. 왼쪽, 오른쪽 깊이의 차이를 비교하여 만약 1보다 크다면 False, 1보다 작다면 왼쪽, 오른쪽 각각에 recursively isBalanced 함수를 부른다.

하지만 함수를 두개나 만드는 이 비루한 코드는 runtime이 굉장히 느리다는 것인데......