(Easy) Balanced Binary Tree

문제

 

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

 

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

 

풀이

class Solution:

def isBalanced(self, root: Optional[TreeNode]) -> bool:

 

  def balance(node):

    if not node:

      return 0

 

    left = balance(node.left)

    right = balance(node.right)

    #트리는 균형잡힌 트리여야한다.

    if left == -1 or right == -1:

      return -1

   

    #왼쪽과 오른쪽의 차가 1을 초과하면 안된다.

    if abs(left - right) > 1:

      return -1

    return max(left, right) + 1

 

  return balance(root) is not -1