[leetcode] Balanced Binary Tree

주어진 트리가 Balanced Binary Tree(height-balanced)인지 확인하는 문제이다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isBalanced(self, root):
        def dfs(node):
            if not node: 
                return 0

            left = dfs(node.left)
            right = dfs(node.right)
	
    		# 왼쪽, 오른쪽 차이가 1이상 날 경우
            if left == -1 or right == -1 or abs(left - right) > 1:
                return -1
            
            # 리프 노드에서 현재 노드까지의 거리
            return max(left, right) + 1
        
        # -1이면 Balanced Tree가 아니므로 False 반환
        return dfs(root) != -1