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

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 我的小作品

欢迎体验我的作品之一：小编辑器-XCompiler
在线编辑器
App Store 搜索即可~

---