时间戳

首页 > 解决方案 > JavaScript - 使用数组或链表更快地计算二叉树的高度

javascript - JavaScript - 使用数组或链表更快地计算二叉树的高度

问题描述

我无法让我的代码在更长的输入（即更高或更宽的树）上运行得更快。它在高度约为 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;
}

标签： javascriptalgorithmlinked-listtreebreadth-first-search

解决方案

因此，创建一个具有父节点编号和高度的结构数组。最初，高度将全部为 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}
}

推荐阅读