Ağac məsələlərinin çoxu iki rekursiv şablondan birinə uyğun gəlir. Hər ikisində baza halı (boş düyün), uşaqlar üzrə rekursiya və nəticənin birləşdirilməsi var. Terminologiya və gəzintilər Ağaclar: terminologiya və gəzintilər mövzusunda, axtarış ağacları isə BST: əlavə və axtarış mövzusundadır.

İki şablon: solda hündürlüklər yuxarı qalxır, sağda qalan cəm aşağı enir
İki şablon: solda hündürlüklər yuxarı qalxır, sağda qalan cəm aşağı enir

İki şablon

  1. Nəticəni qaytar (aşağıdan yuxarı). Funksiya alt-ağac üçün cavabı qaytarır, valideynin cavabı uşaqların cavablarından qurulur: dərinlik 1 + max(left, right)-dır.
  2. Yığ (yuxarıdan aşağı). Vəziyyət parametr kimi aşağı gedir (qalan cəm, BST sərhədləri, cari dərinlik) və ya xarici siyahıya yığılır (bütün yollar, səviyyələr).

Aşağıdakı nümunələrdə kiçik build köməkçisi səviyyələr üzrə siyahıdan ağac qurur, None "düyün yoxdur" deməkdir.

Maksimum dərinlik və düyünlərin sayı (qaytar)

python
from collections import deque

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

def build(values):
    """Level-order list, None means no node: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root

def max_depth(node):
    if node is None:
        return 0                                  # base case
    return 1 + max(max_depth(node.left), max_depth(node.right))

def count(node):
    return 0 if node is None else 1 + count(node.left) + count(node.right)

tree = build([3, 9, 20, None, None, 15, 7])
print("depth:", max_depth(tree), "nodes:", count(tree))
text
depth: 3 nodes: 5

Yol cəmi və bütün yollar (yığ)

has_path_sum qalan cəmi aşağı ötürür və yarpaqda yoxlayır. all_paths cari yolu yığır: əlavə et, rekursiya et, geri qaytar. Bu, geri izləmədəki "seç, araşdır, geri qaytar" ideyasının eynisidir.

python
from collections import deque

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

def build(values):
    """Level-order list, None means no node: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = Node(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = Node(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = Node(values[i])
            queue.append(node.right)
        i += 1
    return root