多叉树的直径

本题需要1个注意的地方：

1. 这是无向树(没有环的无向图)，没有子节点、父节点之分，所以题目给的Tree_edge记录的边的start和end并不一定对应：比如0 -> 1 -> 2 图，可以描述为：[[0, 1], [2, 1]];所以需要重新用邻接表对图进行描述，然后利用dfs进行遍历。(图的路径就是一个节点最大两边的和，树是子树最大的两个路径的和， 树有层次)

   function solve( n ,  Tree_edge ,  Edge_value ) {
    let res = 0;
    const obj= {};
    for (let i=0; i<Tree_edge.length; ++i) {
        const v = Tree_edge[i];
        const w = Edge_value[i] || 0;
        obj[v.start] ? obj[v.start].push([w, v.end]):
                    obj[v.start] = [[w, v.end]];
        obj[v.end] ? obj[v.end].push([w, v.start]):
                    obj[v.end] = [[w, v.start]];
    }
    const dfs = (node, pre, w) => {
        let i=0;
        const arr = [];
        while(i<obj[node].length) {
            if (obj[node][i][1] !== pre) 
                arr.push(dfs(obj[node][i][1], node, obj[node][i][0]));
            ++i;
        }
        arr.push(0, 0); // 防止没有
        const one = Math.max(...arr);
        arr[arr.indexOf(one)] = -Infinity;
        const two = Math.max(...arr);
        if (one + two > res) res = one + two;
        return one + w;
    };
    dfs(Tree_edge[0].start, -1, Edge_value[0]);
    return res;
   }

function solve( n ,  Tree_edge ,  Edge_value ) {
    const tree = buildTree(n, Tree_edge, Edge_value);
    const visited = new Array(n).fill(false);
    const {max} = dfs({tree, visited});
    return max;
}
function buildTree(n, tree_edge, edge_value) {
    const tree = new Array(n).fill(null).map(_ => []);
    for (let i = 0; i < tree_edge.length; i++) {
        const {start, end} = tree_edge[i];
        const edge_val = edge_value[i];
        tree[start].push({child: end, len: edge_val});
        tree[end].push({child: start, len: edge_val});
    }
    return tree; 
}

function dfs({tree, visited, idx = 0, max = 0}) {
    if (tree[idx].length === 0 || visited[idx]) return 0;
    visited[idx] = true;
    let m1 = 0, m2 = 0;
    for (let i = 0; i < tree[idx].length; i++) {
        const {child, len} = tree[idx][i];
        if (visited[child]) continue;
        const res = dfs({tree, visited, idx: child, max: max});
        const distance = res.maxDistance + len;
        max = res.max;
        if (distance >= m1) {
            m2 = m1;
            m1 = distance;
        } else if (distance > m2) {
            m2 = distance;
        }
    }
    max = Math.max(max, m1 + m2);
    return {maxDistance: m1, max: max};
}

/*
 * function Interval(a, b){
 *   this.start = a || 0;
 *   this.end = b || 0;
 * }
 */
function solve( n ,  Tree_edge ,  Edge_value ) {
    let nodes = [];//所有节点的数组形式
    let toZeroArr = [0];//所有节点到零节点的长度集合
    // 0节点到其他节点的长度集合
    function to_0_length(){  
        let node = nodes[0];
        let arrayVal = [];//node到其他节点的总长度集合
        let j = 1;
        while(j < nodes.length){
            let end = nodes[j];
            let length = 0;//当前节点I的总长度
            while(1){
                let index;
                for(index in Tree_edge){
                    if(end == Tree_edge[index][1]){
                        length += Edge_value[index];
                        end = Tree_edge[index][0];
                        break;
                    }
                }
                if(node == Tree_edge[index][0]){
                    break;
                }
            }
            arrayVal.push(length)
            j++;
        }
        return arrayVal;
    }
    //返回共同父亲节点下标
    function commonParentNode(node1,node2){
        let fnode1 = [node1];
        let fnode2 = [node2];
        
        for(let index=0;index<  Tree_edge.length;index++){
            let item = Tree_edge[index];
            if(node1==item[1]){
                fnode1.push(item[0])
                node1 = item[0];
                if(node1==0){
                    break
                }
                index = -1;
            }
        }
        for(let index=0;index<  Tree_edge.length;index++){
            let item = Tree_edge[index];
            if(node2==item[1]){
                fnode2.push(item[0])
                node2 = item[0];
                if(node2==0){
                    break
                }
                index = -1;
            }
        }
        fnode1 = fnode1.reverse();
        fnode2 = fnode2.reverse();
        
        let flag = 0;
        let i = 0;
        while(i<fnode1.length&&i<fnode2.length){
            if(fnode2[i]==fnode1[i]){
                flag = i;
            }
            i++;
        }
        return flag;
    }
    function toOtherNodeMaxLength(node,i){//node节点到其他节点的最大长度
        let arrayVal = [];//node到其他节点的总长度集合
        let j = i+1;
        while(j < nodes.length){
            let  k = commonParentNode(node,nodes[j]);
            arrayVal.push(toZeroArr[j]+toZeroArr[i]-2*toZeroArr[k]);
            j++;
        }
        return Math.max(...arrayVal);
    }
    
    
    Tree_edge = Tree_edge.map((item,index)=>{
        return [item.start,item.end]
    })
    //遍历所有节点 统计出各个节点
    nodes.push(Tree_edge[0][0])
    Tree_edge.map(nodeArr=>{
        nodes.push(nodeArr[1])
    })
    toZeroArr = toZeroArr.concat(to_0_length());
    let maxNodesArr = [Math.max(...toZeroArr)];
    nodes.map((item,index)=>{
        if(index!=0&&index!=nodes.length-1){
            maxNodesArr.push(toOtherNodeMaxLength(item,index));
        }
    })
    return Math.max(...maxNodesArr);
}
module.exports = {
    solve : solve
};