[LeetCode] 124. 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

二叉树的最大路径和。

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注意第二个例子，节点值是会存在负数的。思路是后序遍历，因为路径和总是要包括左孩子val + 右孩子val + 当前节点val（注意不是根节点）。做法跟其他后序遍历的题几乎都一样，也是创建一个全局变量记录最后的结果。注意因为路径和有可能是负的所以创建的全局变量的初始值是Integer.MIN_VALUE。helper函数里面去递归左子树和右子树的时候，记得是跟0比较谁大，因为节点值包括负数，加上小于0的节点只会拖垮最后的结果。全局变量res算的是root.val + left + right，因为路径和是包括那些根节点的；因为是后序遍历，所以helper函数往父节点返回的是左子树和右子树较大的一枝 + 当前节点val。

很多后序遍历的题，最后求的结果跟helper函数往父节点返回的值都是有差别的，这个需要多练习。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     int res;
 3 
 4     public int maxPathSum(TreeNode root) {
 5         // corner case
 6         if (root == null) {
 7             return 0;
 8         }
 9         res = Integer.MIN_VALUE;
10         helper(root);
11         return res;
12     }
13 
14     public int helper(TreeNode root) {
15         if (root == null) {
16             return 0;
17         }
18         int left = Math.max(0, helper(root.left));
19         int right = Math.max(0, helper(root.right));
20         res = Math.max(res, left + right + root.val);
21         return Math.max(left, right) + root.val;
22     }
23 }

JavaScript实现

 1 /**
 2  * @param {TreeNode} root
 3  * @return {number}
 4  */
 5 var maxPathSum = function (root) {
 6     let res = -Infinity;
 7     let helper = function (root) {
 8         if (root == null) return 0;
 9         let left = Math.max(0, helper(root.left));
10         let right = Math.max(0, helper(root.right));
11         // let newPath = root.val + left + right;
12         res = Math.max(root.val + left + right, res);
13         return Math.max(left, right) + root.val;
14     }
15     helper(root);
16     return res;
17 };

LeetCode 题目总结