厦门网站建设网站,网站开发建设哪家好,中国进出口贸易官网,淄博网站建设选择臻动传媒2049. 统计最高分的节点数目
给你一棵根节点为 0 的 二叉树 #xff0c;它总共有 n 个节点#xff0c;节点编号为 0 到 n - 1 。同时给你一个下标从 0 开始的整数数组 parents 表示这棵树#xff0c;其中 parents[i] 是节点 i 的父节点。由于节点 0 是根#xff0c;所以 p…2049. 统计最高分的节点数目
给你一棵根节点为 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 分别是节点 13 和 4 。示例 2输入parents [-1,2,0]
输出2
解释
- 节点 0 的分数为2 2
- 节点 1 的分数为2 2
- 节点 2 的分数为1 * 1 1
最高分数为 2 有两个节点分数为 2 分别为节点 0 和 1 。
提示
n parents.length2 n 10510^5105parents[0] -1对于 i ! 0 有 0 parents[i] n - 1parents 表示一棵二叉树。
解题思路
先创建节点类用来保存二叉树节点之间的关系以及每个节点下属节点的数量递归查找每个节点的后代节点的数量保存在每个节点中每次删除某个节点计算分数的公式为左子树的节点个数 * 右子树的节点个数 * 总节点数-当前子树节点个数。遍历所有节点统计最高得分 节点的 数目 。
代码
class Node{
public:Node *left,*right;int children;};
class Solution {
public:int countHighestScoreNodes(vectorint parents) {mapint,Node* m;for (int i 0; i parents.size(); i) {m[i]new Node();}for (int i 1; i parents.size(); i) {Node *pm[parents[i]],*curm[i];if (p-left! nullptr)p-rightcur;else p-leftcur;}this-totalparents.size();count(m[0]);dfs(m[0]);return maxn;}long long maxx0;int maxn0,total;int count(Node *root){if (root nullptr) return 0;int lcount(root-left),rcount(root-right);return root-children(1lr);}void dfs(Node *root){if (root nullptr) return ;dfs(root-left);dfs(root-right);long long num(long long)(root-left nullptr?1:root-left-children)*(long long)(root-right nullptr?1:root-right-children)*(long long)max(1,total-root-children);if (nummaxx){maxxnum;maxn1;}else if (nummaxx){maxn;}}
};
