[Leetcode 110] - Balanced Binary Tree w/ Python

Given a binary tree, determine if it is height-balanced

 

 

이진 트리가 주어졌을때 균형 이진 트리인지 확인해야 되는 문제

 

 

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

 

 

---

 

 

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true

 

 

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

 

 

Example 3:

Input: root = []
Output: true

 

 

 

---

 

 

 

함수 아웃풋:

[ 현재까지 탐색한 부분이 균형인가 확인 , 현재까지 탐색한 길이 확인]

 

 

 

1. DFS를 통해 Root 노드가 None일때 까지 탐색 → None이면 [True, 0] 리턴

2. 현재 Root 노드에서 Child 노드 각각 길이를 받아서 균형인지 확인

3. 균형이면 [True, 현재 최대 길이 (Ancestor 노드에서 사용되는 값)] 아니면 [False, (무의미한 숫자)]

※ 1을 더하는 이유는 root 노드를 합산해서 나온 결과 

 

 

 

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        
        def dfs(root):
            if not root:
                return [True, 0]
            
            # 왼,오 탐색
            left, right = dfs(root.left), dfs(root.right)
            if left[0] and right[0]: # 둘다 True를 줬다면
                balanced = abs(left[1] - right[1]) < 2 # 이번 root이 균형인가 확인
            else:
                balanced = False # 만약 하나라도 false를 줬다면
            
            return [balanced, max(left[1], right[1]) + 1] # 루트 노드 생각해서 + 1
        
        return dfs(root)[0] # True/False 리턴

 

 

오예