Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 12.3 Задача построения двоичного дерева

Question

Даны прямой обход `preorder` и симметричный обход `inorder` некоторого двоичного дерева. Постройте по ним двоичное дерево и верните его корневой узел. Предполагается, что в дереве нет узлов с одинаковыми значениями (как показано на рисунке 12-5).

Рисунок 12-5 Пример данных для построения двоичного дерева

### 1. Проверка, является ли это задачей «разделяй и властвуй»

Исходная задача - построить двоичное дерево по `preorder` и `inorder` - является типичной задачей для стратегии «разделяй и властвуй».

- Задача раскладывается на части: если смотреть с точки зрения стратегии «разделяй и властвуй», исходную задачу можно разбить на две подзадачи: построение левого поддерева и построение правого поддерева, плюс одно действие: инициализация корневого узла. Для каждого поддерева (подзадачи) можно использовать тот же способ разбиения, пока не будет достигнута наименьшая подзадача (пустое поддерево).
- Подзадачи независимы: левое и правое поддеревья независимы друг от друга и не пересекаются. При построении левого поддерева нам нужно смотреть только на ту часть прямого и симметричного обходов, которая соответствует левому поддереву. Для правого поддерева рассуждение аналогично.
- Решения подзадач можно объединить: когда левое и правое поддеревья (решения подзадач) уже построены, их можно присоединить к корневому узлу и тем самым получить решение исходной задачи.

### 2. Как разделить поддеревья

Из анализа выше видно, что эта задача действительно решается через «разделяй и властвуй», но как именно, имея прямой обход `preorder` и симметричный обход `inorder`, отделить левое и правое поддеревья?

По определению и `preorder` , и `inorder` можно разбить на три части.

- Прямой обход: `[ корневой узел | левое поддерево | правое поддерево ]` , например для дерева на рисунке 12-5 это `[ 3 | 9 | 2 1 7 ]` .
- Симметричный обход: `[ левое поддерево | корневой узел | правое поддерево ]` , например для дерева на рисунке 12-5 это `[ 9 | 3 | 1 2 7 ]` .

На примере данных на рисунке 12-5 разбиение можно выполнить по шагам, показанным на рисунке 12-6.

1. Первый элемент прямого обхода, равный 3, является значением корневого узла.
2. Найти индекс корневого узла 3 в `inorder`. Используя этот индекс, можно разбить `inorder` на `[ 9 | 3 | 1 2 7 ]` .
3. По результату разбиения `inorder` нетрудно определить, что число узлов в левом и правом поддеревьях равно 1 и 3 соответственно, а значит, `preorder` можно разбить как `[ 3 | 9 | 2 1 7 ]` .

Рисунок 12-6 Разбиение поддеревьев в прямом и симметричном обходах

### 3. Описание интервалов поддеревьев через переменные

Согласно описанному выше способу разбиения, мы уже получили интервалы индексов корневого узла, левого и правого поддеревьев в `preorder` и `inorder`. Чтобы описывать эти интервалы, нам понадобится несколько указателей-переменных.

- Обозначим индекс корневого узла текущего дерева в `preorder` через \(i\) .
- Обозначим индекс корневого узла текущего дерева в `inorder` через \(m\) .
- Обозначим интервал индексов текущего дерева в `inorder` через \([l, r]\) .

Как показано в таблице 12-1, этих переменных достаточно для описания индекса корневого узла в `preorder` и интервалов поддеревьев в `inorder` .

Таблица 12-1 Индексы корневого узла и поддеревьев в прямом и симметричном обходах

| Индекс корневого узла в `preorder` | Интервал индексов поддерева в `inorder`
--- | --- | ---
Текущее дерево | \(i\) | \([l, r]\)
Левое поддерево | \(i + 1\) | \([l, m-1]\)
Правое поддерево | \(i + 1 + (m - l)\) | \([m+1, r]\)

Стоит отметить, что \((m-l)\) в индексе корневого узла правого поддерева означает число узлов в левом поддереве. Лучше всего понять это выражение, сопоставив его с тем, что показано на рисунке 12-7.

Рисунок 12-7 Представление индексных интервалов корня и поддеревьев

### 4. Реализация кода

Чтобы ускорить поиск \(m\) , мы используем хеш-таблицу `hmap` для хранения отображения значений массива `inorder` в индексы:

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
build_tree.py

    def dfs(
        preorder: list[int],
        inorder_map: dict[int, int],
        i: int,
        l: int,
        r: int,
    ) -> TreeNode | None:
        """Построить двоичное дерево: разделяй и властвуй"""
        # Завершить при пустом диапазоне поддерева
        if r - l < 0:
            return None
        # Инициализировать корневой узел
        root = TreeNode(preorder[i])
        # Найти m, чтобы разделить левое и правое поддеревья
        m = inorder_map[preorder[i]]
        # Подзадача: построить левое поддерево
        root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
        # Подзадача: построить правое поддерево
        root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)
        # Вернуть корневой узел
        return root

    def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
        """Построить двоичное дерево"""
        # Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        inorder_map = {val: i for i, val in enumerate(inorder)}
        root = dfs(preorder, inorder_map, 0, 0, len(inorder) - 1)
        return root

build_tree.cpp

    /* Построить двоичное дерево: разделяй и властвуй */
    TreeNode *dfs(vector<int> &preorder, unordered_map<int, int> &inorderMap, int i, int l, int r) {
        // Завершить при пустом диапазоне поддерева
        if (r - l < 0)
            return NULL;
        // Инициализировать корневой узел
        TreeNode *root = new TreeNode(preorder[i]);
        // Найти m, чтобы разделить левое и правое поддеревья
        int m = inorderMap[preorder[i]];
        // Подзадача: построить левое поддерево
        root->left = dfs(preorder, inorderMap, i + 1, l, m - 1);
        // Подзадача: построить правое поддерево
        root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
        // Вернуть корневой узел
        return root;
    }

    /* Построить двоичное дерево */
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        unordered_map<int, int> inorderMap;
        for (int i = 0; i < inorder.size(); i++) {
            inorderMap[inorder[i]] = i;
        }
        TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorder.size() - 1);
        return root;
    }

build_tree.java

    /* Построить двоичное дерево: разделяй и властвуй */
    TreeNode dfs(int[] preorder, Map<Integer, Integer> inorderMap, int i, int l, int r) {
        // Завершить при пустом диапазоне поддерева
        if (r - l < 0)
            return null;
        // Инициализировать корневой узел
        TreeNode root = new TreeNode(preorder[i]);
        // Найти m, чтобы разделить левое и правое поддеревья
        int m = inorderMap.get(preorder[i]);
        // Подзадача: построить левое поддерево
        root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
        // Подзадача: построить правое поддерево
        root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
        // Вернуть корневой узел
        return root;
    }

    /* Построить двоичное дерево */
    TreeNode buildTree(int[] preorder, int[] inorder) {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        Map<Integer, Integer> inorderMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        TreeNode root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
        return root;
    }

build_tree.cs

    /* Построить двоичное дерево: разделяй и властвуй */
    TreeNode? DFS(int[] preorder, Dictionary<int, int> inorderMap, int i, int l, int r) {
        // Завершить при пустом диапазоне поддерева
        if (r - l < 0)
            return null;
        // Инициализировать корневой узел
        TreeNode root = new(preorder[i]);
        // Найти m, чтобы разделить левое и правое поддеревья
        int m = inorderMap[preorder[i]];
        // Подзадача: построить левое поддерево
        root.left = DFS(preorder, inorderMap, i + 1, l, m - 1);
        // Подзадача: построить правое поддерево
        root.right = DFS(preorder, inorderMap, i + 1 + m - l, m + 1, r);
        // Вернуть корневой узел
        return root;
    }

    /* Построить двоичное дерево */
    TreeNode? BuildTree(int[] preorder, int[] inorder) {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        Dictionary<int, int> inorderMap = [];
        for (int i = 0; i < inorder.Length; i++) {
            inorderMap.TryAdd(inorder[i], i);
        }
        TreeNode? root = DFS(preorder, inorderMap, 0, 0, inorder.Length - 1);
        return root;
    }

build_tree.go

    /* Построить двоичное дерево: разделяй и властвуй */
    func dfsBuildTree(preorder []int, inorderMap map[int]int, i, l, r int) *TreeNode {
        // Завершить при пустом диапазоне поддерева
        if r-l < 0 {
            return nil
        }
        // Инициализировать корневой узел
        root := NewTreeNode(preorder[i])
        // Найти m, чтобы разделить левое и правое поддеревья
        m := inorderMap[preorder[i]]
        // Подзадача: построить левое поддерево
        root.Left = dfsBuildTree(preorder, inorderMap, i+1, l, m-1)
        // Подзадача: построить правое поддерево
        root.Right = dfsBuildTree(preorder, inorderMap, i+1+m-l, m+1, r)
        // Вернуть корневой узел
        return root
    }

    /* Построить двоичное дерево */
    func buildTree(preorder, inorder []int) *TreeNode {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        inorderMap := make(map[int]int, len(inorder))
        for i := 0; i < len(inorder); i++ {
            inorderMap[inorder[i]] = i
        }

        root := dfsBuildTree(preorder, inorderMap, 0, 0, len(inorder)-1)
        return root
    }

build_tree.swift

    /* Построить двоичное дерево: разделяй и властвуй */
    func dfs(preorder: [Int], inorderMap: [Int: Int], i: Int, l: Int, r: Int) -> TreeNode? {
        // Завершить при пустом диапазоне поддерева
        if r - l < 0 {
            return nil
        }
        // Инициализировать корневой узел
        let root = TreeNode(x: preorder[i])
        // Найти m, чтобы разделить левое и правое поддеревья
        let m = inorderMap[preorder[i]]!
        // Подзадача: построить левое поддерево
        root.left = dfs(preorder: preorder, inorderMap: inorderMap, i: i + 1, l: l, r: m - 1)
        // Подзадача: построить правое поддерево
        root.right = dfs(preorder: preorder, inorderMap: inorderMap, i: i + 1 + m - l, l: m + 1, r: r)
        // Вернуть корневой узел
        return root
    }

    /* Построить двоичное дерево */
    func buildTree(preorder: [Int], inorder: [Int]) -> TreeNode? {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        let inorderMap = inorder.enumerated().reduce(into: [:]) { $0[$1.element] = $1.offset }
        return dfs(preorder: preorder, inorderMap: inorderMap, i: inorder.startIndex, l: inorder.startIndex, r: inorder.endIndex - 1)
    }

build_tree.js

    /* Построить двоичное дерево: разделяй и властвуй */
    function dfs(preorder, inorderMap, i, l, r) {
        // Завершить при пустом диапазоне поддерева
        if (r - l < 0) return null;
        // Инициализировать корневой узел
        const root = new TreeNode(preorder[i]);
        // Найти m, чтобы разделить левое и правое поддеревья
        const m = inorderMap.get(preorder[i]);
        // Подзадача: построить левое поддерево
        root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
        // Подзадача: построить правое поддерево
        root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
        // Вернуть корневой узел
        return root;
    }

    /* Построить двоичное дерево */
    function buildTree(preorder, inorder) {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        let inorderMap = new Map();
        for (let i = 0; i < inorder.length; i++) {
            inorderMap.set(inorder[i], i);
        }
        const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
        return root;
    }

build_tree.ts

    /* Построить двоичное дерево: разделяй и властвуй */
    function dfs(
        preorder: number[],
        inorderMap: Map<number, number>,
        i: number,
        l: number,
        r: number
    ): TreeNode | null {
        // Завершить при пустом диапазоне поддерева
        if (r - l < 0) return null;
        // Инициализировать корневой узел
        const root: TreeNode = new TreeNode(preorder[i]);
        // Найти m, чтобы разделить левое и правое поддеревья
        const m = inorderMap.get(preorder[i]);
        // Подзадача: построить левое поддерево
        root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
        // Подзадача: построить правое поддерево
        root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
        // Вернуть корневой узел
        return root;
    }

    /* Построить двоичное дерево */
    function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        let inorderMap = new Map<number, number>();
        for (let i = 0; i < inorder.length; i++) {
            inorderMap.set(inorder[i], i);
        }
        const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
        return root;
    }

build_tree.dart

    /* Построить двоичное дерево: разделяй и властвуй */
    TreeNode? dfs(
      List<int> preorder,
      Map<int, int> inorderMap,
      int i,
      int l,
      int r,
    ) {
      // Завершить при пустом диапазоне поддерева
      if (r - l < 0) {
        return null;
      }
      // Инициализировать корневой узел
      TreeNode? root = TreeNode(preorder[i]);
      // Найти m, чтобы разделить левое и правое поддеревья
      int m = inorderMap[preorder[i]]!;
      // Подзадача: построить левое поддерево
      root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
      // Подзадача: построить правое поддерево
      root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
      // Вернуть корневой узел
      return root;
    }

    /* Построить двоичное дерево */
    TreeNode? buildTree(List<int> preorder, List<int> inorder) {
      // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
      Map<int, int> inorderMap = {};
      for (int i = 0; i < inorder.length; i++) {
        inorderMap[inorder[i]] = i;
      }
      TreeNode? root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
      return root;
    }

build_tree.rs

    /* Построить двоичное дерево: разделяй и властвуй */
    fn dfs(
        preorder: &[i32],
        inorder_map: &HashMap<i32, i32>,
        i: i32,
        l: i32,
        r: i32,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        // Завершить при пустом диапазоне поддерева
        if r - l < 0 {
            return None;
        }
        // Инициализировать корневой узел
        let root = TreeNode::new(preorder[i as usize]);
        // Найти m, чтобы разделить левое и правое поддеревья
        let m = inorder_map.get(&preorder[i as usize]).unwrap();
        // Подзадача: построить левое поддерево
        root.borrow_mut().left = dfs(preorder, inorder_map, i + 1, l, m - 1);
        // Подзадача: построить правое поддерево
        root.borrow_mut().right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r);
        // Вернуть корневой узел
        Some(root)
    }

    /* Построить двоичное дерево */
    fn build_tree(preorder: &[i32], inorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        let mut inorder_map: HashMap<i32, i32> = HashMap::new();
        for i in 0..inorder.len() {
            inorder_map.insert(inorder[i], i as i32);
        }
        let root = dfs(preorder, &inorder_map, 0, 0, inorder.len() as i32 - 1);
        root
    }

build_tree.c

    /* Построить двоичное дерево: разделяй и властвуй */
    TreeNode *dfs(int *preorder, int *inorderMap, int i, int l, int r, int size) {
        // Завершить при пустом диапазоне поддерева
        if (r - l < 0)
            return NULL;
        // Инициализировать корневой узел
        TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
        root->val = preorder[i];
        root->left = NULL;
        root->right = NULL;
        // Найти m, чтобы разделить левое и правое поддеревья
        int m = inorderMap[preorder[i]];
        // Подзадача: построить левое поддерево
        root->left = dfs(preorder, inorderMap, i + 1, l, m - 1, size);
        // Подзадача: построить правое поддерево
        root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r, size);
        // Вернуть корневой узел
        return root;
    }

    /* Построить двоичное дерево */
    TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        int *inorderMap = (int *)malloc(sizeof(int) * MAX_SIZE);
        for (int i = 0; i < inorderSize; i++) {
            inorderMap[inorder[i]] = i;
        }
        TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorderSize - 1, inorderSize);
        free(inorderMap);
        return root;
    }

build_tree.kt

    /* Построить двоичное дерево: разделяй и властвуй */
    fun dfs(
        preorder: IntArray,
        inorderMap: Map<Int?, Int?>,
        i: Int,
        l: Int,
        r: Int
    ): TreeNode? {
        // Завершить при пустом диапазоне поддерева
        if (r - l < 0) return null
        // Инициализировать корневой узел
        val root = TreeNode(preorder[i])
        // Найти m, чтобы разделить левое и правое поддеревья
        val m = inorderMap[preorder[i]]!!
        // Подзадача: построить левое поддерево
        root.left = dfs(preorder, inorderMap, i + 1, l, m - 1)
        // Подзадача: построить правое поддерево
        root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r)
        // Вернуть корневой узел
        return root
    }

    /* Построить двоичное дерево */
    fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
        // Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
        val inorderMap = HashMap<Int?, Int?>()
        for (i in inorder.indices) {
            inorderMap[inorder[i]] = i
        }
        val root = dfs(preorder, inorderMap, 0, 0, inorder.size - 1)
        return root
    }

build_tree.rb

    ### Построить двоичное дерево: разделяй и властвуй ###
    def dfs(preorder, inorder_map, i, l, r)
      # Завершить при пустом диапазоне поддерева
      return if r - l < 0

      # Инициализировать корневой узел
      root = TreeNode.new(preorder[i])
      # Найти m, чтобы разделить левое и правое поддеревья
      m = inorder_map[preorder[i]]
      # Подзадача: построить левое поддерево
      root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
      # Подзадача: построить правое поддерево
      root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)

      # Вернуть корневой узел
      root
    end

    ### Построить двоичное дерево ###
    def build_tree(preorder, inorder)
      # Инициализировать хеш-таблицу для хранения соответствия элементов inorder их индексам
      inorder_map = {}
      inorder.each_with_index { |val, i| inorder_map[val] = i }
      dfs(preorder, inorder_map, 0, 0, inorder.length - 1)
    end

Визуализация кода

Во весь экран >

На рисунке 12-8 показан рекурсивный процесс построения двоичного дерева: каждый узел создается в фазе «спуска», а каждое ребро (ссылка) формируется в фазе «подъема».

<1><2><3><4><5><6><7><8><9>

Рисунок 12-8 Рекурсивный процесс построения двоичного дерева

Результаты разбиения `preorder` и `inorder` внутри каждого рекурсивного вызова показаны на рисунке 12-9.

Рисунок 12-9 Результаты разбиения в каждом рекурсивном вызове

Пусть число узлов дерева равно \(n\). Инициализация каждого узла (то есть выполнение одного рекурсивного вызова `dfs()` ) занимает \(O(1)\) времени. Следовательно, общая временная сложность равна \(O(n)\) .

Хеш-таблица хранит отображение значений `inorder` в индексы, поэтому ее пространственная сложность равна \(O(n)\) . В худшем случае, когда двоичное дерево вырождается в связный список, глубина рекурсии достигает \(n\) и требует \(O(n)\) памяти стека. Следовательно, общая пространственная сложность также равна \(O(n)\) .

##### Оставляйте свои идеи, вопросы и предложения в комментариях