Skip to main content

Posts

Showing posts from October, 2021

Graph - Medium Level - Question 1

Graph - Medium Level - Question 1 Leetcode 2049. Count Nodes With the Highest Score There is a binary tree rooted at 0 consisting of n nodes. The nodes are labeled from 0 to n - 1. You are given a 0-indexed integer array parents representing the tree, where parents[i] is the parent of node i. Since node 0 is the root, parents[0] == -1. Each node has a score. To find the score of a node, consider if the node and the edges connected to it were removed. The tree would become one or more non-empty subtrees. The size of a subtree is the number of the nodes in it. The score of the node is the product of the sizes of all those subtrees. Return the number of nodes that have the highest score. Constraints: n == parents.length 2 <= n <= 10^5 parents[0] == -1 0 <= parents[i] <= n - 1 for i != 0 parents represents a valid binary tree. Analysis: If we have had the binary tree, then we just can do a top-down count, to count the number of nodes for the sub-tree with the root as the curren