[파이썬 알고리즘 인터뷰][트리] 균형 이진 트리

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

로그 재정렬 기준

1.  

 

책에서 구현된 코드

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check(root):
            if not root:
                return 0

            left = check(root.left)
            right = check(root.right)
            # 높이 차이가 나는 경우 -1, 이외에는 높이에 따라 1 증가
            if left == -1 or \
                    right == -1 or \
                    abs(left - right) > 1:
                return -1
            return max(left, right) + 1

        return check(root) != -1

 

기억해야할 기법

• DFS에서 결과가 나오면 연산을 중지하도록 설계
  
  • left나 right가 -1이면 바로 -1 반환

 

내가 구현한 코드

class Solution:
    result = True
    def isBalanced(self, root: TreeNode) -> bool:
        def dfs(node: TreeNode):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            self.result = self.result and abs(left-right) <= 1
            return max(left,right)+1
        dfs(root)
        return self.result

• 책에서 구현한 방법 과 같이 균형이 깨진 결과(-1)가 한 번이라도 나오면
  • abs(left-right)를 안하고 -1을 바로 return
  • 계산양이 줄어 속도가 더 빠른듯