[리트코드] 110. 균형 이진 트리 (Python)

Balanced Binary Tree - LeetCode

문제

입력으로 받은 트리가 균형 트리인지 확인하고 True, False를 출력하라

 

과정

• 가장 아래 노드부터 0으로 시작해 왼쪽, 오른쪽 노드의 깊이가 얼마나 차이나는지 확인한다.
• 이때, 균형 트리의 정의에 따라 양쪽 자식 노드에 계산된 값의 차이가 1 초과가 되면 그 트리는 균형 트리가 될 수 없다. 

 

입력

[3,9,20,null,null,15,7]

출력

true

 

풀이

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if not root:
                return 0
            
            left = dfs(root.left)
            right = dfs(root.right)
            
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            return max(left, right) + 1
        
        return dfs(root) != -1

 

한 줄 씩 해석해보기

def dfs(root):
    if not root:
        return 0

• dfs 함수에 root를 넣어준다.
• 만약 root에 값이 없다면 0을 return한다.

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

• 가장 아래 노드부터 0으로 시작해 왼쪽, 오른쪽 노드의 깊이가 얼마나 차이나는지 확인한다.

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

• 만약 left가 -1 이거나 right가 -1 또는 left - right의 절대값이 1보다 크다면 -1을 return한다.
• 양쪽 자식 노드에 계산된 값의 차이가 1 초과가 되면 그 트리는 균형 트리가 될 수 없다. 

    return max(left, right) + 1

• left와 right 중 가장 큰 값에 1을 더해준다.

return dfs(root) != -1

• dfs(root)가 -1이 아니면 True를 return한다.