[Python/leetcode]110. Balanced Binary Tree

https://leetcode.com/problems/balanced-binary-tree/

이 문제는 DFS를 이용해서 가장 아래 트리노드에서부터 올라가는 방식으로 풀 수 있다. answer를 기록하는 방식에 아이디어가 필요했는데 처음에는 비효율적인 방법으로 기록했지만 최종적으로 리뷰한 방법은 클래스 변수인 answer에 Bool 타입을 기록하는 것이다. 단 한번이라도 조건을 충족하지 못하면 answer 변수에 False를 기록할 수 있다.
예외 조건이 하나 있는데, 초기 값으로 NoneType 값, 즉 아무런 초기값이 없는 root 노드가 주어지면 정답을 True처리 한다.

한 가지만 더 효율적으로 하고 싶은게 있는데 바로 False가 한번 이라도 등장하면 프로그램을 종료하고 싶다는 것이다. 그 방법을 아직은 모르겠다.

class Solution:
    answer = True
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        def dfs(node)->int:
            if not node:
                return -1
            l = dfs(node.left)
            r = dfs(node.right)
            if abs(l -r) > 1:
                self.answer = False
            return max(l, r) + 1
        dfs(root)
        return self.answer