统计最高分的节点数目
题目地址： 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;};
复制代码
评论