牛客233052题递归解法解析：二叉树最大路径和问题

7个月前 (08-06)牛客题解279

一、问题理解与算法概述

二叉树最大路径和问题要求找出二叉树中任意节点到任意节点的路径，使得路径上的节点值之和最大。这个问题考察了对二叉树的理解和递归算法的应用能力。

二、完整代码实现

#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;  // 空节点贡献值为0
    
    // 递归计算左右子树的最大贡献值（负数则取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) {
        int parent_idx = parents[i] - 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);
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
    }
    
    vector<int> parents(n);
    for (int i = 0; i < n; ++i) {
        cin >> parents[i];
    }
    
    TreeNode* root = buildTree(values, parents);
    cout << maxPathSum(root) << endl;
    
    return 0;
}