这题说的是找出二叉树的最大路径和，这里的最大路径不一定经过根节点，所以我们可以采用自下往上的遍历方式来计算， 对于当前节点：
- 如果它的两个子节点路径都是负的，就没必要选择了，因为如果是负数，越选择和就会越小，如下图中的第 1 种情况。
- 如果它的两个子节点路径一个是正的，一个是负的，我们只需要选择正的即可，如下图中的第 2 种情况。
- 如果它的两个子节点都是正的，我们可以都选择，也可以选择其中的一个子节点，如下图中的第 3 种情况。
最后我们只需要保存选择的最大值即可，对于第 1 ，2 两种情况，我们还可以接着往上继续选择，但对于第 3 种情况，如果两个子节点都选择了，就不能再往上选了，分支会出现分叉。
private int ans = Integer.MIN_VALUE;// 默认个给个最小值
public int maxPathSum(TreeNode root) {
dfs(root);
return ans;
}
public int dfs(TreeNode root) {
if (root == null)
return 0;
int left = dfs(root.left);// 左子节点的值
int right = dfs(root.right); // 右子节点的值
// 第1,2种情况，左右子节点最多只能选择一个
int res = root.val + Math.max(0, Math.max(left, right));
// 第3种情况，左右子节点可以都选择。
int cur = root.val + Math.max(0, left) + Math.max(0, right);
// 记录最大值
ans = Math.max(ans, Math.max(cur, res));
// 第1,2种情况还可以再计算，所以返回的是res
return res;
}
int ans = INT_MIN;// 默认个给个最小值
public:
int maxPathSum(TreeNode *root) {
dfs(root);
return ans;
}
int dfs(TreeNode *root) {
if (root == nullptr)
return 0;
int left = dfs(root->left);// 左子节点的值
int right = dfs(root->right); // 右子节点的值
// 第1,2种情况，左右子节点最多只能选择一个
int res = root->val + max(0, max(left, right));
// 第3种情况，左右子节点可以都选择。
int cur = root->val + max(0, left) + max(0, right);
// 记录最大值
ans = max(ans, max(cur, res));
// 第1,2种情况还可以再计算，所以返回的是res
return res;
}
京公网安备 11010502036488号