110. Balanced Binary Tree

Problem Statement

link: https://leetcode.com/problems/balanced-binary-tree/ https://leetcode.cn/problems/balanced-binary-tree/

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

Example:

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

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

Input: root = [] Output: true

Solution Approach

The solution uses a depth-first search (DFS) to assess each subtree’s balance, terminating early if any part is found unbalanced.

Algorithm

1. DFS Recursive Function: The check function returns the depth if a subtree is balanced, and -1 otherwise.
2. Depth Evaluation: For each node, the function evaluates the balance of its left and right subtrees, and if either is unbalanced, the -1 value is propagated upwards.
3. Balanced Tree Check: The isBalanced function determines tree balance by seeing if the root’s evaluation through check equals -1.

Implement

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

 

    
    

Twitter  facebook  Email