九章算法 | Facebook 面试题：The Barycentre of The Trees
撰文 | JZ
专栏 | 九章算法
题目描述
对于一棵多叉树，如果有一个结点 R，以R为根，其所有子树的最大子树的结点数最少，则称结点 R 为这棵树的重心。现在给你一棵有 n 个结点的多叉树，求这棵树的重心，如果有多个重心，则返回编号最小的。x[i], y[i]代表第 i 条边的两个点。
思路点拨
随意选择一个点作为树的根节点，比如 1 结点。dp[i] 代表以 i 为根的子树的结点个数。dp[i] = sum(dp[j]) + 1，则以 i 为根的子树的最大结点个数为 max(max(dp[j]), n - dp[i])。
考点分析
本题实质上就是一个树形dp，一次dfs就能求出每个节点的子树大小，那么n - dp[i]就是另一个方向子树的大小，这样就可以求出以这个点为根的最大子数的大小，维护一下答案即可。
九章参考程序
https://www. jiuzhang.com/solution/t he-barycentre-of-the-trees/