Python Coding 面接の質問と回答

Question: Implement a function to check if a binary tree is balanced.

class TreeNode:
 def __init__(self, value):
 self.value = value
 self.left = None
 self.right = None

def is_balanced(root):
 if root is None:
 return True
 left_height = height(root.left)
 right_height = height(root.right)
 return abs(left_height - right_height) <= 1 and is_balanced(root.left) and is_balanced(root.right)

def height(node):
 if node is None:
 return 0
 return max(height(node.left), height(node.right)) + 1

Example: