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}
}

现在，从列表中的第一项开始，找到它的父项。如果父节点的高度不为零，则节点的高度比父节点的高一。否则，找到parent的parent，看看是否设置了它的height等。

您使用堆栈来跟踪您访问过的节点。

算法看起来像这样:

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}
}