Деревья и обходы

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

def build(values):
    """Из списка по уровням (как в LeetCode): None — пустое место."""
    if not values or values[0] is None:
        return None
    nodes = [TreeNode(v) if v is not None else None for v in values]
    kids = iter(nodes[1:])
    for node in nodes:
        if node:
            node.left, node.right = next(kids, None), next(kids, None)
    return nodes[0]

def show(node, depth=0):
    """Печать дерева, повёрнутого на 90°: корень слева, правые потомки сверху."""
    if node:
        show(node.right, depth + 1)
        print("      " * depth + str(node.val))
        show(node.left, depth + 1)

root = build([8, 3, 10, 1, 6, None, 14, None, None, 4, 7, 13])
show(root)

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

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))

def preorder(node):                 # узел → левое → правое: копирование, сериализация
    if not node:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

def inorder(node):                  # левое → узел → правое: в BST — по возрастанию
    if not node:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

def postorder(node):                # левое → правое → узел: удаление, вычисление размеров
    if not node:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

print("pre: ", preorder(root))
print("in:  ", inorder(root))
print("post:", postorder(root))

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

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))

def preorder_iter(root):
    result, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.right:                  # правый кладём первым — достанем вторым
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

def inorder_iter(root):
    result, stack, node = [], [], root
    while stack or node:
        while node:                     # спускаемся влево до упора
            stack.append(node)
            node = node.left
        node = stack.pop()
        result.append(node.val)
        node = node.right
    return result

print(preorder_iter(root), inorder_iter(root))

from collections import deque

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

root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(6)))

def level_order(root):
    if not root:
        return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):     # ровно столько узлов, сколько на текущем уровне
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        result.append(level)
    return result

levels = level_order(root)
print(levels)
print("вид справа:", [lvl[-1] for lvl in levels])
print("уровней:", len(levels), "| сумма по уровням:", [sum(lvl) for lvl in levels])

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

root = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))), TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1))))

def size(node):
    return 0 if not node else 1 + size(node.left) + size(node.right)

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

def mirror(node):
    if node:
        node.left, node.right = mirror(node.right), mirror(node.left)
    return node

def has_path_sum(node, target):
    if not node:
        return False
    if not node.left and not node.right:            # лист
        return node.val == target
    rest = target - node.val
    return has_path_sum(node.left, rest) or has_path_sum(node.right, rest)

def is_balanced(node):
    def check(n):                                   # высота или -1, если не сбалансировано
        if not n:
            return 0
        l, r = check(n.left), check(n.right)
        if l < 0 or r < 0 or abs(l - r) > 1:
            return -1
        return 1 + max(l, r)
    return check(node) >= 0

print(size(root), height(root), has_path_sum(root, 22), is_balanced(root))

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

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root

def search(root, val):
    node = root
    while node and node.val != val:
        node = node.left if val < node.val else node.right
    return node is not None

def inorder(node):
    return inorder(node.left) + [node.val] + inorder(node.right) if node else []

def kth_smallest(root, k):
    stack, node = [], root
    while True:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right

root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)
print(inorder(root))                  # симметричный обход BST — отсортированный порядок
print(search(root, 6), search(root, 5), kth_smallest(root, 3))

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["$"] = True                         # конец слова

    def _find(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def contains(self, word):
        node = self._find(word)
        return bool(node and node.get("$"))

    def complete(self, prefix):
        node, result = self._find(prefix), []
        def walk(n, path):
            for ch, child in n.items():
                if ch == "$":
                    result.append(prefix + path)
                else:
                    walk(child, path + ch)
        if node:
            walk(node, "")
        return sorted(result)

t = Trie()
for w in ["кот", "котёнок", "кофе", "код", "дом"]:
    t.insert(w)
print(t.contains("кот"), t.contains("ко"), t.complete("ко"))