给定父节点创建树,求最大路径和
作者:
Sakura1996
,
2024-06-12 13:07:46
,
所有人可见
,
阅读 15
#include <iostream>
#include <climits>
#include <vector>
using namespace std;
int res = INT_MIN;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* createTree(vector<int> valList, vector<int> fatherList) {
vector<TreeNode*> nodeList;
for (auto val : valList) {
nodeList.push_back(new TreeNode(val));
}
for (int i = 1; i < fatherList.size(); i ++) {
if (nodeList[fatherList[i] - 1]->left == nullptr) {
nodeList[fatherList[i] - 1]->left = nodeList[i];
} else {
nodeList[fatherList[i] - 1]->right = nodeList[i];
}
}
return nodeList[0];
}
int dfs(TreeNode* root)
{
if (!root) return 0;
auto left = max(0, dfs(root->left)), right = max(0, dfs(root->right));
res = max(res, root->val + left + right);
return root->val + max(left, right);
}
int main() {
int n;
cin >> n;
vector<int> valList(n, 0);
vector<int> fatherList(n, 0);
for (int i = 0; i < n; i ++) {
cin >> valList[i];
}
for (int i = 0; i < n; i ++) {
cin >> fatherList[i];
}
auto root = createTree(valList, fatherList);
dfs(root);
cout << res << endl;
return 0;
}