48. Balanced Binary Tree

🎯 leetcode - 110. Balanced Binary Tree

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 48번 문제

📌 날짜

2020.02.17

📌 시도 횟수

2 try

💡 Code

class Solution:
    is_balanced = True

    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(root: TreeNode):
            if root is None:
                return -1

            left = dfs(root.left)
            right = dfs(root.right)
            left += 1
            right += 1

            if abs(left - right) >= 2:
                self.is_balanced = False

            return max(left, right)

        dfs(root)
        return self.is_balanced

💡 문제 해결 방법

- 43번 문제의 코드를 조금 변형해서 만들었다.
- 재귀 호출로 리프 노드까지 내려간다. 
- 위의 그림처럼 각 노드에 상태값을 지정해주었다.
- 만약 현재 노드를 기준으로 left 상태값과 right 상태값의 차가 1보다 크면,
이 이진트리는 균형 이진트리가 아니다. 따라서 클래스 변수 is_balanced를 False로 바꾼다.
- 모든 dfs 탐색이 끝나고, is_balanced를 리턴한다.

💡 새롭게 알게 된 점

- is_balanced를 클래스 변수가 아닌 isBalanced 함수 내 변수로 설정했더니
값이 적용되지 않았다. 따라서 값의 변경을 위해 클래스 변수로 만들었다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. 간단한 재귀 풀이

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(root: TreeNode):
            if root is None:
                return 0

            left = dfs(root.left)
            right = dfs(root.right)

            if left == -1 or right == -1 or abs(left - right) >= 2:
                return -1

            return max(left, right) + 1

        return dfs(root) != -1

💡 문제 해결 방법

- 내 풀이를 조금 변형한 풀이이다.
- 위의 풀이에서는 리프노드의 상태값이 1부터 시작하도록 지정해 주었다. 따라서
>> if root is None: return 0
- 재귀 호출로 리프노드까지 내려가고, max(left, right) + 1를 반환해
상위 노드로 이동할수록 자식 노드의 최대 깊이보다 1씩 증가시켜 depth를 구한다.
- 하지만 만약 left와 right의 차가 1보다 크면 -1을 리턴한다.
- 이렇게 한번 -1이 리턴되면 더 이상 회복이 안된다. 
>> if left == -1 or right == -1 or abs(left - right) >= 2:
>>     return -1
- 따라서 만약 한번이라도 -1을 리턴했다면, 최종적으로 리턴되는 값도 -1이다.
- 즉, return dfs(root) != -1을 통해 만약 균형이진트리가 아니면 -1이 반환되므로
False를 리턴할 수 있게 된다.

💡 새롭게 알게 된 점

-