题目来自LeetCode中，链接为124. 二叉树中的最大路径和


一棵树的最大路径和可能存在于哪里：

1. 单纯的存在于以左子树为根节点的子树中
2. 单纯的存在于以右子树为根节点的子树中
3. 根节点到达左子树B中某节点的路径
4. 根节点到达右子树C中某节点的路径
5. 左子树中某节点到达右子树中某节点的路径，必然经过根节点
6. 根节点(假如左、右子树的最大路径均为负数)

因为需要获得从根节点到达其子树中某节点的路径和，很容易想到是深度优先遍历。又因为计算以根节点的树的最大路径和计算其左子树、右子树中的最大路径和函数功能相同，所以设计为递归算法。

定义递归函数DFS(root)，返回值为经过root节点的单边最大值(单边最大值为root到达其某个子孙节点的最大值，或者root节点自身，即情况3、4、6)。

剩下的情况1、2、5的最大值需要用一个变量 maxpath 来统计。

因此可以得到如下代码：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int maxpath;int dfs(TreeNode* root){if(root == nullptr) return 0;//计算左边分支最大值，左边分支如果为负数还不如不选择int left = max(0, dfs(root->left));  //计算右边分支最大值，右边分支如果为负数还不如不选择int right = max(0, dfs(root->right));  //left->root->right 作为路径与历史最大值做比较maxpath = max(maxpath, left + right + root->val);  // 返回经过root的单边最大分支给上游return root->val + max(left, right);  }int maxPathSum(TreeNode* root) {maxpath = -INT_MAX;dfs(root);return maxpath;}
};

另外一道类似的题目，其唯一的区别在于需要考虑输入自己构造一棵树：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;int n, maxpath;
int arr[100010][3];  //三列分别为左孩子、右孩子和valint dfs(int root) {if (root == 0) return 0;  //根结点为空int left = max(0, dfs(arr[root][0]));int right = max(0, dfs(arr[root][1]));maxpath = max(maxpath, left + right + arr[root][2]);return arr[root][2] + max(left, right);
}int main() {cin >> n;for (int i = 1; i <= n; i++) {cin >> arr[i][0] >> arr[i][1] >> arr[i][2];}maxpath = -INT_MAX;dfs(1);cout << maxpath << endl;return 0;
}