【牛客233052题解析】二叉树**路径和：动态规划与递归算法详解

胡志明t

一、题目解读

牛客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-1定位父节点索引，依次连接左右子树（若父节点无左子节点则挂左，否则挂右）。

3. 计算**路径和：

○ 调用maxPathSum(root)，初始化max_sum=INT_MIN。

○ 递归遍历树，每次计算left/right子树的**贡献，更新max_sum为三者之和（root.val + left + right）。

○ 最终返回max_sum作为全局**值。

4. 输出结果：cout打印**路径和。

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <climits>
   
4. #include <algorithm>
   
5. using namespace std;
   
6. 
   
7. struct TreeNode {
   
8.     int val;
   
9.     TreeNode* left;
   
10.     TreeNode* right;
    
11.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 节点构造
    
12. };
    
13. 
    
14. int maxPathSumHelper(TreeNode* root, int& max_sum) { // 递归计算**路径和（含当前节点）
    
15.     if (!root) return 0; // 递归终止条件
    
16.     int left = max(maxPathSumHelper(root->left, max_sum), 0); // 左子树**贡献（忽略负值）
    
17.     int right = max(maxPathSumHelper(root->right, max_sum), 0); // 右子树同理
    
18.     max_sum = max(max_sum, root->val + left + right); // 更新全局**值（当前节点+左右子树）
    
19.     return root->val + max(left, right); // 返回以当前节点为起点的单向**路径
    
20. }
    
21. 
    
22. int maxPathSum(TreeNode* root) { // 主计算函数
    
23.     int max_sum = INT_MIN;
    
24.     maxPathSumHelper(root, max_sum);
    
25.     return max_sum;
    
26. }
    
27. 
    
28. TreeNode* buildTree(const vector<int>& values, const vector<int>& parents) { // 根据值和父节点构建树
    
29.     if (values.empty()) return nullptr;
    
30.     vector<TreeNode*> nodes(values.size());
    
31.     for (int i = 0; i < values.size(); ++i) {
    
32.         nodes[i] = new TreeNode(values[i]); // 创建节点
    
33.     }
    
34.     for (int i = 1; i < parents.size(); ++i) { // 从第二个节点开始连接（根节点索引为0）
    
35.         int parent_idx = parents[i] - 1; // 父节点索引（题目索引从1开始，需减1）
    
36.         if (parent_idx >= 0) { // 防止索引越界
    
37.             if (!nodes[parent_idx]->left) { // 若父节点无左子节点
    
38.                 nodes[parent_idx]->left = nodes[i];
    
39.             } else { // 否则挂右子节点
    
40.                 nodes[parent_idx]->right = nodes[i];
    
41.             }
    
42.         }
    
43.     }
    
44.     return nodes[0]; // 返回根节点
    
45. }
    
46. 
    
47. int main() {
    
48.     int n;
    
49.     cin >> n; // 输入节点数
    
50.     vector<int> values(n), parents(n); // 存储节点值和父节点索引
    
51.     for (int i = 0; i < n; ++i) {
    
52.         cin >> values[i];
    
53.     }
    
54.     for (int i = 0; i < n; ++i) {
    
55.         cin >> parents[i];
    
56.     }
    
57.     TreeNode* root = buildTree(values, parents); // 构建树
    
58.     cout << maxPathSum(root) << endl; // 输出**路径和
    
59.     return 0;
    
60. }

复制代码

五、总结

1. 算法核心：动态规划结合递归，通过“自底向上”计算子树贡献，避免重复遍历。

2. 关键优化：利用max(0, subtreemax)过滤负贡献路径，确保路径和为正。

3. 复杂度分析：时间O(n)（单次遍历树），空间O(n)（递归栈或全局变量）。

4. 拓展思考：可进一步优化空间复杂度至O(1)，但需修改递归逻辑。

5. 应用场景：适用于树形结构的**路径问题，如股票买卖、资源分配等变体题目。

来源：【牛客233052题解析】二叉树**路径和：动态规划与递归算法详解