void MaxPathSum(TreeNode* root, int& pathSum, int& maxSum, vector<int>& currentPath, vector<int>& maxPath) {
if(root == 0) {
return;
}
pathSum += root->data;
currentPath.push_back(root->data);
if(root->left == 0 && root->right == 0) {
if(maxSum < pathSum) {
maxPath = currentPath;
maxSum = pathSum;
}
} else {
MaxPathSum(root->left, pathSum, maxSum, currentPath, maxPath);
MaxPathSum(root->right, pathSum, maxSum, currentPath, maxPath);
}
pathSum -= root->data;
currentPath.pop_back();
}
vector<int> MaxPathSum(TreeNode* root) {
vector<int> maxPath;
int maxSum = INT32_MIN;
vector<int> currentPath;
int pathSum = 0;
MaxPathSum(root, pathSum, maxSum, currentPath, maxPath);
cout << maxSum << endl;
return maxPath;
}
