Преобразовать массив в binary tree

Question

У меня есть массив чисел представляющий бинарное дерево:

var data = new object[] { 1, 2, 3, 4, null, null, 5 };

и мне надо перевести его в классическую форму:

(каждое число - это по порядку center, left, right. Если null - пропускаем узел)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

И я вроде как придумал способ построения, который выдаёт нужный результат:

private TreeNode CreateTree(object[] data)
{
    TreeNode[] nodes = data.Select(x => x == null ? null : new TreeNode((int)x, null, null)).ToArray();

    int current = 0;
    bool left = true;

    for (int i = 1; i < nodes.Length; i++)
    {
        if (left)
        {
            nodes[current].left = nodes[i];
            left = false;
        }
        else
        {
            nodes[current].right = nodes[i];
            left = true;

            current++;
            while (current < nodes.Length  && nodes[current] == null)
                current++;
        }
    }

    return nodes[0];
}

Но что-то мне кажется, что это какой-то кривой велосипед и можно как-то изящнее совместить обход в ширину (BFS / LOT) с обходом в глубину (DFS Preorder: center, left, right).

Кто-нибудь знает, как подобная задача решается по классике?

Answer 1

Ну, как варианты

Линейный обход (с конца)

Это похоже на BFS, только в обратном порядке.

private TreeNode CreateTree(object[] data)
{
    var nodes = new Dictionary<int, TreeNode>();

    for (int i = data.Length - 1; i >= 0; i--)
    {
        object val = data[i];
        if (val == null) continue;
        int index = i + 1;

        nodes.TryGetValue(index * 2, out TreeNode left);
        nodes.TryGetValue(index * 2 + 1, out TreeNode right);

        var node = new TreeNode((int)val, left, right);
        nodes[index] = node;
    }

    nodes.TryGetValue(1, out TreeNode root);    
    return root;
}

Фишка в том, что вот это bool left = true; вам не надо, так как левый или правый узел можно понять по индексу узла.

Вывод идентичный вашему.

DFS стиль

Простенькая рекурсия.

private TreeNode CreateTreeDFS(object[] data)
{
    return CreateTreeDFS(data, 0);
}

private TreeNode CreateTreeDFS(object[] data, int index)
{
    if (index < 0 || index >= data.Length) return null;
    
    var val = data[index];
    if (val == null) return null;
    
    return new TreeNode((int)val, CreateTreeDFS(data, (index + 1) * 2 - 1), CreateTreeDFS(data, (index + 1) * 2));
}

Вывод идентичный вашему.

BFS стиль

Самый стремный имхо, так как перед проходом надо создавать все узлы заранее.

private TreeNode CreateTreeBFS(object[] data)
{
    var nodes = new Dictionary<int, TreeNode>();

    for (int i = 0; i < data.Length; i++)
    {
        object val = data[i];
        if (val == null) continue;
        int index = i + 1;
        
        var node = new TreeNode((int)val, null, null);
        nodes[index] = node;
    }
    
    foreach(var key in nodes.Keys)
    {
        nodes.TryGetValue(key * 2, out TreeNode left);
        nodes.TryGetValue(key * 2 + 1, out TreeNode right);
        
        var node = nodes[key];
        node.left = left;
        node.right = right;
    }

    nodes.TryGetValue(1, out TreeNode root);
    return root;
}

Linq вариант для создания узлов

private TreeNode CreateTreeBFS(object[] data)
{
    var nodes = data.Select((v, ind) => (v, ind))
        .Where(x => x.v != null)
        .ToDictionary(x => x.ind +1, x => new TreeNode((int)x.v, null, null));

    foreach (var key in nodes.Keys)
    {
        nodes.TryGetValue(key * 2, out TreeNode left);
        nodes.TryGetValue(key * 2 + 1, out TreeNode right);

        var node = nodes[key];
        node.left = left;
        node.right = right;
    }

    nodes.TryGetValue(1, out TreeNode root);
    return root;
}

Вывод идентичный вашему.

БЛОГ НА HUSL

Преобразовать массив в binary tree

Ответы (1 шт):

Линейный обход (с конца)

DFS стиль

BFS стиль