For each node, compute the height of its left and right subtrees separately, then check if they differ by more than 1. Recurse on every node in the tree. This recalculates heights repeatedly, leading to redundant work.
Use a single DFS pass that returns the height of each subtree, or -1 if any subtree is unbalanced. This avoids redundant height calculations by propagating the imbalance signal upward.
""" 0110.1 - Solution 1 - Top-Down Recursive """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def isBalanced(self, root: Optional[TreeNode]) -> bool:
"""Check if tree is height-balanced (top-down)"""
if not root:
return True
left_height = self.height(root.left)
right_height = self.height(root.right)
if abs(left_height - right_height) > 1:
return False
return self.isBalanced(root.left) and self.isBalanced(root.right)
def height(self, node: Optional[TreeNode]) -> int:
"""Compute height of a subtree"""
if not node:
return 0
return 1 + max(self.height(node.left), self.height(node.right))
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: [3,9,20,null,null,15,7] -> True
root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(Solution().isBalanced(root1)) # True
# Example 2: [1,2,2,3,3,null,null,4,4] -> False
root2 = TreeNode(1,
TreeNode(2, TreeNode(3, TreeNode(4), TreeNode(4)), TreeNode(3)),
TreeNode(2))
print(Solution().isBalanced(root2)) # False
# Example 3: [] -> True
print(Solution().isBalanced(None)) # True
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0110.2 - Solution 2 - Bottom-Up DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def isBalanced(self, root: Optional[TreeNode]) -> bool:
"""Check if tree is height-balanced (bottom-up)"""
return self.dfs(root) != -1
def dfs(self, node: Optional[TreeNode]) -> int:
"""Return height if balanced, -1 if not"""
if not node:
return 0
left = self.dfs(node.left)
if left == -1:
return -1
right = self.dfs(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return 1 + max(left, right)
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: [3,9,20,null,null,15,7] -> True
root1 = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(Solution().isBalanced(root1)) # True
# Example 2: [1,2,2,3,3,null,null,4,4] -> False
root2 = TreeNode(1,
TreeNode(2, TreeNode(3, TreeNode(4), TreeNode(4)), TreeNode(3)),
TreeNode(2))
print(Solution().isBalanced(root2)) # False
# Example 3: [] -> True
print(Solution().isBalanced(None)) # True
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()