## 题目地址

https://leetcode.com/problems/binary-tree-maximum-path-sum/

## 题目描述

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

``````Input: [1,2,3]

1
/ \
2   3

Output: 6
``````

Example 2:

``````Input: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

Output: 42
``````

## 思路

``````    4
/ \
11 13
/ \
7   2
``````

``````class Solution {
public:
int maxPathSum(TreeNode* root) {
int res = INT_MIN;
helper(root, res);
return res;
}
int helper(TreeNode* node, int& res) {
if (!node) return 0;
int left = max(helper(node->left, res), 0);
int right = max(helper(node->right, res), 0);
res = max(res, left + right + node->val);
return max(left, right) + node->val;
}
};
``````

### 思路2

1. 第一是跟节点必须选择
2. 第二是左右子树只能选择一个

• 递归
• 理解题目中的path定义

## 代码

``````

/*
* @lc app=leetcode id=124 lang=javascript
*
* [124] Binary Tree Maximum Path Sum
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
*     this.val = val;
*     this.left = this.right = null;
* }
*/
if (node === null) return 0;

node.val + Math.max(0, l) + Math.max(0, r),
);

return node.val + Math.max(l, r, 0);
}
/**
* @param {TreeNode} root
* @return {number}
*/
var maxPathSum = function(root) {
if (root === null) return 0;
max: root.val
};