深度遍历：统计最高分的节点数目 🐟

统计最高分的节点数目

题目地址： https://leetcode-cn.com/problems/count-nodes-with-the-highest-score/

题目描述：

给你一棵根节点为 0 的 二叉树 ，它总共有 n 个节点，节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1。

一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的 分数 。求出某个节点分数的方法是，将这个节点和与它相连的边全部删除，剩余部分是若干个非空子树，这个节点的分数为所有这些子树 大小的乘积 。

请你返回有 最高得分 节点的 数目 。

示例

输入：parents = [-1,2,0,2,0]
输出：3
解释：
- 节点 0 的分数为：3 * 1 = 3
- 节点 1 的分数为：4 = 4
- 节点 2 的分数为：1 * 1 * 2 = 2
- 节点 3 的分数为：4 = 4
- 节点 4 的分数为：4 = 4
最高得分为 4 ，有三个节点得分为 4 （分别是节点 1，3 和 4 ）。

输入：parents = [-1,2,0]
输出：2
解释：
- 节点 0 的分数为：2 = 2
- 节点 1 的分数为：2 = 2
- 节点 2 的分数为：1 * 1 = 1
最高分数为 2 ，有两个节点分数为 2 （分别为节点 0 和 1 ）。

题目分析

本题其实一开始题目都要看很久，才明白具体的目的。 计算节点的其实就是在二叉树中移除该节点后，至多会剩下三个二叉树：左子树，右子树，父树。然后将这剩下的二叉树上面的节点数量相乘，得到此节点的分数。

以[-1,2,0,2,0]的index2节点为例，移除产生了三个树，然后分数为1*1*2 = 2

以index4节点为例，移除只有父树，分数为4 * 1 * 1 = 4

ps: 如果没有左右子树，计算时左右子树节点数算作1

可以先写一个add1方法，如果传入为0，则返回1

function add1(n) {
    if (n == 0) return 1;
    return n;
}

并且父树的节点数量其实就是总节点数 - 左子节点数 - 右子节点数 - 1 （1是其本身）

可以创建一个childrenArr二维数组，代表每个节点拥有的子节点，[[leftindex1, rightindex1],[leftindex2, rightindex2],...]

let childrenArr = parents.map(()=>{
    return [];
})
parents.forEach((item, i)=>{
    if (item != -1) {
        childrenArr[item].push(i);
    }
})   

以[-1,2,0,2,0]为例子，就是[ [ 2, 4 ], [], [ 1, 3 ], [], [] ]

构建深度遍历方法，如果此节点有左右子树，将左右子树的起点递归遍历，最终返回值为左右子树节点数目和，并且对相应的数组赋值。

代码

var countHighestScoreNodes = function(parents) {
    // maxScore: 最大分数  totalnums：最终数目
    let maxScore = 0, alllen = parents.length, totalnums = 0;
    // 每个节点左右父树的节点数量
    let leftArr = [], rightArr = [], parentsArr = [];
    // childrenArr：每个节点拥有的子节点，[[leftindex1, rightindex1],[leftindex2, rightindex2],...]
    let childrenArr = parents.map(()=>{
        return [];
    })
    parents.forEach((item, i)=>{
        if (item != -1) {
            childrenArr[item].push(i);
        }
    })    
    // 深度遍历方法
    function TotalNums(i) {
        let leftNums = 0, rightNums = 0, parentNums = 0;
        // 已经有了此节点数据
        if (leftArr[i] != undefined) {
            return leftArr[i] + rightArr[i];
        }
        // 如果有左子节点树
        if (childrenArr[i] && childrenArr[i].length >= 1) {
            let larr = TotalNums(childrenArr[i][0]);
            leftNums = leftNums + larr + 1
        }
        // 如果有右子节点树
        if (childrenArr[i] && childrenArr[i].length == 2) {
            let rarr = TotalNums(childrenArr[i][1])
            rightNums = rightNums + rarr + 1
        }
        // 父树
        parentNums = alllen - 1 - leftNums - rightNums;
        leftArr[i] = leftNums, rightArr[i] = rightNums, parentsArr[i] = parentNums;

        let score = add1(leftArr[i]) * add1(rightArr[i]) * add1(parentsArr[i]);
        
        if (score > maxScore) {
             maxScore = score;
             totalnums = 1;
        } else if (score == maxScore) {
            totalnums++;
        }
        return leftNums + rightNums;
    }
    function add1(n) {
        if (n == 0) return 1;
        return n;
    }
    for(let i = 0; i < alllen; i++) {
        if (leftArr[i] == undefined) {
            TotalNums(i);
        }
    }
    return totalnums;
};