JavaScript - быстрее вычисляет высоту дерева, используя массив или связанный список

Question

Я не могу заставить мой код работать быстрее на длинных входах, то есть на более высоких или более широких деревьях. Это терпит неудачу на деревьях высотой около 1000. Кто-нибудь может предложить какие-либо изменения в мой код или любые другие алгоритмы, чтобы этот код работал быстрее?

Вопрос - Вам дано описание корневого дерева. Ваша задача - вычислить и вывести его высоту. Отзыв что высота (корневого) дерева - это максимальная глубина узла или максимальное расстояние от лист до корня. Вам дано произвольное дерево, не обязательно двоичное дерево.

Формат ввода. Первая строка содержит количество узлов ?. Вторая строка содержит ? целых чисел от −1 до ? - 1 - родители узлов. Если ?-й из них (0 ≤ ? ≤ ? - 1) равен -1, узел ? является корнем, в противном случае это основанный на 0 индекс родителя ?-го узла. Гарантируется, что существует ровно один корень. Гарантируется, что вход представляет дерево.

Ограничения. 1 ≤ ? ≤ 105

Формат вывода. Вывод высоты дерева.

Образец 1. Входные данные:
5
4 -1 4 1 1

Выход:
3

Код с использованием подхода связанного списка и обхода BFS -

var readline = require('readline');
var input = [];

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('line', function (cmd) {
    input.push(cmd);
});

rl.on('close', function (cmd) {
    input=input[1].split(" ");

    let tree1=list_to_tree(input);
    console.log( height(tree1));
    process.exit(0);
});

function list_to_tree(list) 
{
    var map = [], node, roots = [], i;
    for(i=0;i<list.length;i++)
    {
        map.push([{[i] :list[i],
            children:[]
        }]);
    }

    for(i=0;i<list.length;i++)
    {
        node=map[i];
        if(list[i]!==-1 && list[i]!=="-1")
        {
            map[list[i]][0]["children"].push(node);
        }
        else {roots.push(node);}
    }

    return roots[0];
}

function height(tree)
{ 
    let h=0;
    if (tree===null)return;
    let  q=[];
    q.push(tree);
    while(q.length>0)
    {
        let l =q.length;
        while (l--)
        {
            let node=q.shift();
            q.push(...node[0]["children"]);
        }
        h++;
    }

    return h;
}

Код с использованием массива -

var readline = require('readline');

var input = [];

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('line', function (cmd) {
    input.push(cmd);
});

rl.on('close', function (cmd) {
   input=input[1].split(" ");

    let tree1=list_to_tree(input);
    console.log( height(tree1));
    process.exit(0);
});

function list_to_tree(list) {
    let map=[];roots=[];
    for (var x=0;x<list.length;x++){
        map[2*x]=x;
        map[2*x+1]=[];
    }
    for(var x=0;x<list.length;x++){
        node=map.slice(2*x,2*x+2);
        if(list[x]==-1){
            roots.push(...node);}
        else {
            map[2*list[x]+1].push(...node);
        }
    }

    return roots;
}

function height(tree) {
    if(tree==null){return 0;}
    let q=[];
    q.push(...tree);
    let h=0;
    while(q.length>0){
        let l=q.length/2;
        while(l--){
            q.shift();
            child=q.shift();
            q.push(...child);
        }
        h++;
    }
    return h;
}

Answer 1

Итак, создайте массив структур, которые имеют номер родительского узла и высоту. Изначально все высоты будут равны 0, за исключением корня, высота которого вы установили равным 1. Учитывая ваш пример ввода, у вас есть:

[
    {4, 0},
    {-1, 1},
    {4, 0},
    {1, 0},
    {1, 0}
}

Теперь, начиная с первого элемента в списке, найдите его родителя. Если высота родителя не равна нулю, то высота узла на единицу больше, чем высота родителя. В противном случае найдите родителя родителя и посмотрите, установлена ​​ли его высота и т. Д.

Вы используете стек для отслеживания посещенных вами узлов.

Алгоритм выглядит примерно так:

for each index, n
    while a[n].height == 0
        stack.push(n)
        n = a[n].parent
    parent = n;
    while !stack.isEmpty()
        stack.pop(n)
        a[n].height = a[parent].height + 1
        parent = n

На данный момент все высоты узлов установлены. Вы можете отсканировать массив, чтобы найти максимальную высоту.

Очевидной оптимизацией является отслеживание максимальной высоты при сканировании дерева. То есть после очистки стека вы делаете это:

    if (a[n].height > max_height)
        max_height = a[n].height;

Учитывая ваш ввод, мы начинаем с узла 0. Его высота равна 0, поэтому вы помещаете 0 в стек и смотрите на узел 4. Его высота также равна 0, поэтому вы смотрите на узел 1. Его высота равна 1, поэтому Вы выталкиваете стек и назначаете узлу 4 значение высоты 2. Затем вы снова выталкиваете стек и назначаете узлу 0 высоту 3. В итоге вы получите:

[
    {4, 3},
    {-1, 1},
    {4, 0},
    {1, 0},
    {1, 2}
}

Узел 1 уже имеет свою высоту. Узел 2 имеет высоту 0, поэтому вы нажимаете на него и смотрите на узел 4. Его высота равна 2, поэтому вы извлекаете стек и назначаете узлу 2 значение высоты 3.

Узел 3 имеет высоту 0, поэтому вы смотрите на его родителя, который имеет высоту 1. Таким образом, высота узла 3 равна 2. Наконец, вы смотрите на узел 4, высота которого уже установлена. Ваш результат:

[
    {4, 3},
    {-1, 1},
    {4, 3},
    {1, 2},
    {1, 2}
}