LeetCode编程题解法汇总|力扣解法汇总2049-统计最高分的节点数目算法|图论|leetcode

原题链接：力扣
描述：给你一棵根节点为 0 的二叉树，它总共有 n 个节点，节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树，其中 parents[i] 是节点 i 的父节点。由于节点 0 是根，所以 parents[0] == -1 。
一个子树的大小为这个子树内节点的数目。每个节点都有一个与之关联的分数。求出某个节点分数的方法是，将这个节点和与它相连的边全部删除，剩余部分是若干个非空子树，这个节点的分数为所有这些子树大小的乘积。
请你返回有最高得分节点的数目。

示例 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 ）。
示例 2：
输入：parents = [-1,2,0]
输出：2
解释：
- 节点 0 的分数为：2 = 2
- 节点 1 的分数为：2 = 2
- 节点 2 的分数为：1 * 1 = 1
最高分数为 2 ，有两个节点分数为 2 （分别为节点 0 和 1 ）。

提示：
n == parents.length
2 <= n <= 105
parents[0] == -1
对于 i != 0 ，有 0 <= parents[i] <= n - 1
parents 表示一棵二叉树。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-nodes-with-the-highest-score
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

* 解题思路： * 这题长度10^5，那么时间复杂度一定不能超过O(NlgN)，目标还是往O(N)靠拢。 * 我的想法是构建一个一个的Node节点，每个节点包含left,right,parent的id，以及leftNum和rightNum的数量。 * 第一步，我们构建所有的节点，用map记录。方便根据id查找该节点。 * 第二步，我们遍历数组，根据parent分别给parentNode的left和right赋值，以及给node节点的parent赋值。 * 第三步，从根节点开始递归遍历，找到left的节点数量leftNum,right的节点数量rightNum.如果某个节点的leftNum>0，则证明计算过，无需重复计算。其实应该也不会出现重复计算的场景，毕竟是从上向下有序的。 * 第四步，再次遍历数组。获取对应的node节点。因为我们有其leftNum,rightNum，则可以计算出parentNum。则value=https://www.it610.com/article/leftNum*rightNum*parentNum; * 第五步，如果value>maxvalue，则maxvaluenum=1。如果value=https://www.it610.com/article/=maxvalue，则maxvaluenum++。最终返回maxvaluenum即可

代码：

public class Solution2049 {public int countHighestScoreNodes(int[] parents) { Map map = new HashMap<>(); //1,2 for (int i = 0; i < parents.length; i++) { Node node = new Node(); node.value = https://www.it610.com/article/i; map.put(i, node); } for (int i = 0; i < parents.length; i++) { int parent = parents[i]; Node parentNode = map.get(parent); if (parentNode == null) { continue; } if (parentNode.left == -1) { parentNode.left = i; continue; } parentNode.right = i; Node node = map.get(i); node.parent = parent; } int num = searchList(map.get(0), map); long maxValue = 0; int maxValueNum = 0; for (int i = 0; i < parents.length; i++) { Node node = map.get(i); long leftNum = node.leftNum; long rightNum = node.rightNum; long topNum = num - leftNum - rightNum - 1; topNum = topNum == 0 ? 1 : topNum; leftNum = leftNum == 0 ? 1 : leftNum; rightNum = rightNum == 0 ? 1 : rightNum; long value = leftNum * rightNum * topNum; if (value> maxValue) { maxValueNum = 1; maxValue = https://www.it610.com/article/value; } else if (value == maxValue) { maxValueNum++; } } return maxValueNum; }private int searchList(Node node, Map map) { int leftNum = 0; int rightNum = 0; if (node.left >= 0) { if (node.leftNum > 0) { leftNum = node.leftNum; } else { leftNum = searchList(map.get(node.left), map); } } if (node.right >= 0) { if (node.rightNum > 0) { rightNum = node.rightNum; } else { rightNum = searchList(map.get(node.right), map); } } node.leftNum = leftNum; node.rightNum = rightNum; return leftNum + rightNum + 1; }static class Node { int value = https://www.it610.com/article/-1; int leftNum = 0; int rightNum = 0; int parent = -1; int left = -1; int right = -1; }}

【LeetCode编程题解法汇总|力扣解法汇总2049-统计最高分的节点数目】