قطر الأشجار وارتفاعها وتوازنها

ارتفاع الشجرة الثنائية

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

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root))  # 4

القطر: أطول مسار

def diameter_of_binary_tree(root):
    max_diameter = [0]  # use list to allow closure mutation

    def dfs(node):
        if not node:
            return 0
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # Diameter through this node
        max_diameter[0] = max(max_diameter[0], left_h + right_h)
        return 1 + max(left_h, right_h)  # height for parent

    dfs(root)
    return max_diameter[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root))  # 3

مرور DFS واحد لحساب القطر

# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
    if not root:
        return 0
    through_root = height(root.left) + height(root.right)
    in_left = diameter_naive(root.left)
    in_right = diameter_naive(root.right)
    return max(through_root, in_left, in_right)

# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')

التحقق من توازن الشجرة الثنائية

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        if left == -1:
            return -1  # propagate early exit
        right = check(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1  # unbalanced here
        return 1 + max(left, right)  # height if balanced

    return check(root) != -1

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5)  # too deep on left
print(is_balanced(root))  # False

نمط القيمة الحارسة المُعادة

# General pattern: return (is_valid, computed_value)
def balanced_height(node):
    if not node:
        return True, 0
    left_ok, left_h = balanced_height(node.left)
    if not left_ok:
        return False, 0  # short-circuit
    right_ok, right_h = balanced_height(node.right)
    if not right_ok:
        return False, 0
    balanced = abs(left_h - right_h) <= 1
    return balanced, 1 + max(left_h, right_h)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h)  # True 2

القطر بحسب العقد والحواف

def diameter_in_nodes(root):
    max_path = [0]

    def dfs(node):
        if not node:
            return 0
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # Path through this node in NODE count
        nodes_through = left_h + right_h + 1
        max_path[0] = max(max_path[0], nodes_through)
        return 1 + max(left_h, right_h)

    dfs(root)
    return max_path[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root))  # 4 nodes: 4-2-1-3 or 5-2-1-3

مجموع المسار: أي مسار من الجذر إلى ورقة

def has_path_sum(root, target):
    if not root:
        return False
    # Leaf node: check if we've exactly hit the target
    if not root.left and not root.right:
        return root.val == target
    remaining = target - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22))  # True: 5+4+11+2=22

أقصى مجموع لمسار (الحالة الصعبة)

def max_path_sum(root):
    max_sum = [float('-inf')]

    def gain(node):
        if not node:
            return 0
        # Only take positive contributions
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        # Best path through this node (can't go both ways upward)
        max_sum[0] = max(max_sum[0], node.val + left + right)
        # Return the best single-branch gain for parent
        return node.val + max(left, right)

    gain(root)
    return max_sum[0]

root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root))  # 42: 15+20+7

أشجار AVL والتوازن الذاتي

# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node

# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root

# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')

التحقق من تماثل الشجرة

def is_symmetric(root):
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right)

sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym))  # True

nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym))  # False

دمج مفهومي الارتفاع والقطر

# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
    result = [float('-inf')]  # or 0 depending on problem

    def dfs(node):
        if not node:
            return 0  # base return (height, count, etc.)
        left_val = dfs(node.left)
        right_val = dfs(node.right)
        # --- Update global result using both children ---
        candidate = left_val + right_val  # example: diameter
        result[0] = max(result[0], candidate)
        # --- Return info needed by PARENT ---
        return 1 + max(left_val, right_val)  # example: height

    dfs(root)
    return result[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root))  # diameter = 2

تحقق سريع

مراجعة الدرس