# 2049. Count Nodes With the Highest Score
###### tags: `leetcode` `2049` `medium`

## :memo: Question

## :memo: 題意
* 給你一個 array => [-1, 2, 0, 2, 0] 表示一個 binary tree
* index = 0 為 root
* index = 1, value = 2 => 表示 node 1 的 parent 為 2
* index = 2, value = 0 => 表示 node 2 的 parent 為 0
* 求任意拿掉一個 node 剩下 forest nodes 乘起來為最大值的有幾個？

## :memo: leetcode solution
* :medal: **思考一**: 根據 parents array 怎麼 build tree
* :medal: **思考二**: 當拿掉目前的 node 後還剩下哪些部分？是不是要考慮左子樹有多少 nodes ？ 右子樹有多少 nodes？ parents 有多少 nodes?

## :memo: my solution code

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        self.ans = []
        self.total_node = len(parents)
        # buil graph
        # for each time I remove one element
        node = {}
        for i in range(len(parents)):
            node[i] = TreeNode(i)
        
        for i in range(1, len(parents)):
            if not node[parents[i]].left:
                node[parents[i]].left = node[i]
            elif not node[parents[i]].right:
                node[parents[i]].right = node[i]
                
        self.dfs(node[0])
        ans = collections.Counter(self.ans)
        return ans[max(ans.keys())]

    def dfs(self, node):
        if not node:
            return 0

        l_node_num = self.dfs(node.left)  
        r_node_num = self.dfs(node.right)
        pre_node_num = self.total_node - l_node_num - r_node_num - 1
        self.ans.append((1 if not l_node_num else l_node_num) * (1 if not r_node_num else r_node_num) * (1 if not pre_node_num else pre_node_num))

        return l_node_num + r_node_num + 1
                

## :memo: BigO
* 時間複雜度: O(n)。
* 空間複雜度: O(n)。

## :memo: 類似題
* https://hackmd.io/@jLkUSydIQI6gATYn6N7MVw/rkKYF8UT3