【二叉树】统计最高分的节点数目

0x00 题目

给你一棵根节点为 ​

​0​

​​ 的 二叉树

它总共有 ​​

​n​

​​ 个节点

节点编号为 ​​

​0​

​​ 到 ​

​n - 1​

​​ 同时给你一个下标从 ​

​0​

​ 开始的整数数组 ​

​parents​

​ 表示这棵树

其中 ​

​parents[i]​

​ 是节点 ​

​i​

​ 的父节点

由于节点 ​

​0​

​ 是根，所以 ​

​parents[0] == -1​

​

一个子树的 ​

​大小​

​​ 为这个子树内节点的​

​数目​

​​ 每个节点都有一个与之关联的 分数

求出某个节点分数的方法是

将这个节点和与它相连的边全部 删除

剩余部分是若干个 非空 子树

这个节点的 分数 为所有这些子树 大小的​

​乘积​

​

请你返回有 ​

​最高得分​

​ 节点的 数目

0x01 思路

删除一个节点最多把整颗树分割成​

​三​

​​部分：

​​

​左​

​​子树、​

​右​

​​子树、​

​父​

​​节点及父节点的另一半子树

遍历每个节点的左右子树的数目

第三部分的数量就等于

​​

​总​

​​节点数 减去 ​

​左右​

​​子树的数目 再减 ​

​1​

​​ 三者​

​相乘​

​就是分数

没有的部分用 ​

​1​

​ 代替

0x02 解法

语言：​

​Swift​

​

树节点：​

​TreeNode​

​

public class TreeNode {
    public var val: Int
    public var left: TreeNode?
    public var right: TreeNode?
    public init() { self.val = 0; self.left = nil; self.right = nil; }
    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
        self.val = val
        self.left = left
        self.right = right
    }
}      

func countHighestScoreNodes(_ parents: [Int]) -> Int {
    let count = parents.count
    var maxScore: Int = 0
    var ans: Int = 0
    var nodes: [Int:TreeNode] = [:]
    
    func dfs(_ root: TreeNode?) -> Int {
        guard let root = root else { return 0 }
        
        // 左
        let leftCount = dfs(root.left)
        // 右
        let rightCount = dfs(root.right)
        // 剩下部分
        let threeCount = count - leftCount - rightCount - 1
        
        let left = leftCount == 0 ? 1 : leftCount
        let right = rightCount == 0 ? 1 : rightCount
        let three = threeCount == 0 ? 1 : threeCount
        
        // 乘积
        let score = left * right * three
        if score == maxScore {
            ans += 1
        }else if score > maxScore {
            maxScore = score
            ans = 1
        }
        return leftCount + rightCount + 1
    }
    
    // 构建二叉树
    for i in 0..<count {
        nodes[i] = TreeNode()
    }
    for i in 1..<count {
        let child = nodes[i]
        let parent = nodes[parents[i]]!
        if parent.left == nil {
            parent.left = child
        }else{
            parent.right = child
        }
    }
    
    _ = dfs(nodes[0])
    
    return ans
}      

0x03 我的小作品