【牛客233052题解析】二叉树最大路径和：动态规划与递归算法详解
一、题目解读
牛客233052题要求构建一棵二叉树，并计算其中任意路径节点值之和的最大值。题目输入包含两个数组：values（节点值）和parents（父节点索引），需根据这些信息构建树结构，并求解最大路径和。路径定义为任意从根到叶或任意两点间的连续节点序列，需考虑路径方向（单向或双向）。
二、解题思路
采用动态规划+递归的解法，核心思想为“自底向上”计算节点贡献。关键点如下：
1. 构建二叉树：通过buildTree函数利用父节点索引建立树结构，利用vector<TreeNode*>存储节点并连接左右子树。
2. 递归计算最大路径和：
○ maxPathSumHelper递归函数计算以当前节点为起点的最大路径和（单向）。
○ 递归时分别计算左/右子树的最大贡献（含当前节点），并忽略负贡献（max(0, left/right)防止负数影响总路径）。
○ 通过max_sum全局变量记录全局最大值，更新公式为root.val + left + right（即左右子树均包含的最大路径）。
3. 时间优化：递归中避免重复计算，仅递归到叶子节点，最终返回以当前节点为根的单向最大路径。
三、解题步骤
1. 输入处理：通过cin读取节点值values和父节点索引parents，构建二叉树根节点root。
2. 构建树结构：调用buildTree，利用parents[i]-1定位父节点索引，依次连接左右子树（若父节点无左子节点则挂左，否则挂右）。
3. 计算最大路径和：
○ 调用maxPathSum(root)，初始化max_sum=INT_MIN。
○ 递归遍历树，每次计算left/right子树的最大贡献，更新max_sum为三者之和（root.val + left + right）。
○ 最终返回max_sum作为全局最大值。
4. 输出结果：cout打印最大路径和。
四、代码与注释
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 节点构造
};
int maxPathSumHelper(TreeNode* root, int& max_sum) { // 递归计算最大路径和（含当前节点）
if (!root) return 0; // 递归终止条件
int left = max(maxPathSumHelper(root->left, max_sum), 0); // 左子树最大贡献（忽略负值）
int right = max(maxPathSumHelper(root->right, max_sum), 0); // 右子树同理
max_sum = max(max_sum, root->val + left + right); // 更新全局最大值（当前节点+左右子树）
return root->val + max(left, right); // 返回以当前节点为起点的单向最大路径
}
int maxPathSum(TreeNode* root) { // 主计算函数
int max_sum = INT_MIN;
maxPathSumHelper(root, max_sum);
return max_sum;
}
TreeNode* buildTree(const vector<int>& values, const vector<int>& parents) { // 根据值和父节点构建树
if (values.empty()) return nullptr;
vector<TreeNode*> nodes(values.size());
for (int i = 0; i < values.size(); ++i) {
nodes[i] = new TreeNode(values[i]); // 创建节点
}
for (int i = 1; i < parents.size(); ++i) { // 从第二个节点开始连接（根节点索引为0）
int parent_idx = parents[i] - 1; // 父节点索引（题目索引从1开始，需减1）
if (parent_idx >= 0) { // 防止索引越界
if (!nodes[parent_idx]->left) { // 若父节点无左子节点
nodes[parent_idx]->left = nodes[i];
} else { // 否则挂右子节点
nodes[parent_idx]->right = nodes[i];
}
}
}
return nodes[0]; // 返回根节点
}
int main() {
int n;
cin >> n; // 输入节点数
vector<int> values(n), parents(n); // 存储节点值和父节点索引
for (int i = 0; i < n; ++i) {
cin >> values[i];
}
for (int i = 0; i < n; ++i) {
cin >> parents[i];
}
TreeNode* root = buildTree(values, parents); // 构建树
cout << maxPathSum(root) << endl; // 输出最大路径和
return 0;
}五、总结
1. 算法核心：动态规划结合递归，通过“自底向上”计算子树贡献，避免重复遍历。
2. 关键优化：利用max(0, subtreemax)过滤负贡献路径，确保路径和为正。
3. 复杂度分析：时间O(n)（单次遍历树），空间O(n)（递归栈或全局变量）。
4. 拓展思考：可进一步优化空间复杂度至O(1)，但需修改递归逻辑。
5. 应用场景：适用于树形结构的最优路径问题，如股票买卖、资源分配等变体题目。
原创内容 转载请注明出处
