[Python] [LeetCode] Balanced Binary Tree (균형 이진 트리)

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

Balanced Binary Tree - LeetCode

문제 설명:

이진트리가 주어지면 균형 잡힌 이진트리인지 확인하고 True/False 반환한다.

 

처음 시도를 했지만, 제출해보니 문제를 잘못 이해하고 있었다.

처음 이해한건 왼쪽 노드의 가장 맨 왼쪽으로 이동하며 높이를 계산하고

오른쪽 노드의 가장 맨 오른쪽으로 이동하여 높이를 계산하여 두 높이차를 구하는 방법인줄 알았다.

 

•  풀이 방법
  • 이진트리를 만들어 방향성('left')와 함께 넘겨주어 왼쪽노드만 계속 탐색하며 리프노드에 도달할때까지 높이(left_depth)를 더해준다.
  • 이진트리를 만들어 방향성('right')와 함께 넘겨주어 오른쪽노드만 계속 탐색하며 리프노드에 도달할때까지 높이(right_depth)를 더해준다. 

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        left_depth, right_depth = 0, 0
        def dfs(root, direction):
            nonlocal left_depth, right_depth
            if root is None:
                return

            if direction == 'left':
                if root.left and root.left.val:
                    left_depth += 1
                    dfs(root.left, 'left')
            elif direction == 'right':
                if root.right and root.right.val:
                    right_depth += 1
                    dfs(root.right, 'right')
            return

        dfs(root, 'left')
        dfs(root, 'right')
        if abs(left_depth - right_depth) <= 1:
            return True
        else:
            return False

실행을 할 때는 통과했지만 제출을 하니 다음 케이스에서 실패했다.

[1,2,3,4,5,6,null,8]

 

다시 풀어본다. 노드가 있으면 값을 올려주는 방식으로 왼쪽과 오른쪽의 차이가 1을 넘을때 -1을 return 하도록 한다.

class Solution:
    def isBalanced(self, root: Optional[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

위의 이진트리로 예시를 들어보면 

left = check(root.left) 재귀가 먼저 실행되기 때문에 1,2,3,4 리프노드까지 내려간다.

4까지 왔을때 재귀함수가 실행되고 리턴될때 0을 반환한다. left, right 모두 0이기 때문에

max(left, right) + 1 로 1의 숫자를 올려받는다.

 

다시 3으로 돌아왔을때 4에서 올려진 값으로 left =1 을 가지며 right은 올려받은 값이 없기때문에 0을 가진다.

결국 1로 돌아왔을때 left = -1 right = -1이 올려지기 때문에 1도 -1 값을 가진다.

 

다음 그래프의 경우 -1이기 때문에 False 을 반환한다.