C++---树形DP---树的中心（每日一道算法2023.7.19）

**树形DP——树的中心**

每日一道算法2023.7.19**题目描述**

给定一个二叉树，每个节点都有一个权值。求出这个树的中心，即最远离叶子结点的点。

**示例**

输入：[1,2,4,null,5,3]

输出：[4,2]

**解决方案**

我们可以使用树形动态规划（Tree DP）来解决这个问题。首先，我们需要定义一个函数 `dfs` 来计算每个节点的距离和权值。

cppstruct TreeNode {
 int val;
 TreeNode *left;
 TreeNode *right;
};

class Solution {
public:
 vector<int> getCenter(TreeNode* root) {
 if (!root) return {};
 // 计算根节点的距离和权值 int dist =0, sum = root->val;
 dfs(root,1, dist, sum);
 // 找到最远离叶子结点的点 vector<int> res;
 findCenter(root, dist, res);
 return res;
 }
private:
 void dfs(TreeNode* node, int depth, int& dist, int& sum) {
 if (!node) return;
 // 更新距离和权值 dist = max(dist, depth);
 sum += node->val;
 // 递归计算子节点的距离和权值 dfs(node->left, depth +1, dist, sum);
 dfs(node->right, depth +1, dist, sum);
 }
 void findCenter(TreeNode* node, int dist, vector<int>& res) {
 if (!node) return;
 // 如果当前点是最远离叶子结点的点，添加到结果中 if (dist == getDist(node)) res.push_back(node->val);
 // 递归找出子节点是否是最远离叶子结点的点 findCenter(node->left, dist +1, res);
 findCenter(node->right, dist +1, res);
 }
 int getDist(TreeNode* node) {
 if (!node) return INT_MAX;
 // 计算当前点到叶子结点的距离 int left = getDist(node->left), right = getDist(node->right);
 return max(left, right) +1;
 }
};