当前位置：首页 > 牛客 > 【牛客233052题解析】二叉树最大路径和：动态规划与递归算法详解

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

2天前

一、题目解读

牛客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;
}