题目链接

题目描述：

给定一个非空二叉树，返回其最大路径和。

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

实例：
124二叉树中的最大路径和 - 图1

解题思路

  本题属于leetcode hard难度，我认为主要的难度在于你是否真的理解了题意。剩下的就是熟能生巧了～另外，本题与求树的高度和路径一脉相承，有时间可以自行整理～共勉！
  题目定义最大路径和是树内任意一条路径，不必必须经过根结点。以实例为例，9,-10，15,20,7,9,-10,20,15都可以是一条路径，不过9,-10,20,15,7并不是一条路径。其实这类由类似单链表构成的树结构的一大特点就是只能自顶向下遍历，无法返回，比如父结点可以访问其对应的子结点，但是其子结点要再想回去就不行了。讲到此时，有人就会想到本题是否就恰好需要子结点”返回“父结点，进一步来说就是我们常说的回溯。下面我们就来说说为什么要用回溯思想。
  回溯思想无外乎就是”条条大路通罗马，此路不通再换一路”，重点在于如何保存我们需要的上一条路的信息来应用于下一路，简言之就是状态重置。扯远了～回到本题，既然树中任何符合父子结构的路径都可能是路径最大和，那么假设我们遍历到了某一结点，如果路径最大和就包括当前结点，现在我们来捋一捋最大和的可能情况：

  1. 当前结点+当前结点的左子树最大和+当前结点的右子树最大和
  2. 当前结点+当前结点的左子树最大和+当前结点的父结点(递归考虑，可以是父节点的父节点…)+已确定的父节点的另一子树的最大和
  3. 当前结点+当前结点的右子树最大和+当前结点的父结点(递归考虑，可以是父节点的父节点…)+已确定的父节点的另一子树的最大和

  由上述三种情况我们可以归纳总结，1属于常规思维，不会牵扯到它的父结点，事实上也是求树的高度以及叶子路径的思路。不过2、3就不一样了，我们会发现这两种情况会存在子结点将状态传递回给父结点的操作，这就是为什么我们要用到回溯的思想！
  经过上面的情况论述，我们需要自底向上遍历来获取结果，这就要用到后序遍历递归框架，主要核心还是在于对当前结点的处理，也就是对三种情况的处理，其余的交给递归去做。
  针对这三种情况我们可以分成两部分讨论——1和2、3。对于1，我们只需在求和(root->val + leftMax + rightMax)后更新最大路径和maxSum即可。对于2、3，我们要做的就是如何保存当前状态传递给上一层结点，可以设置一个变量temp用于获得经过当前结点的最大路径和，然后返回给上一层即可。一定注意经过当前结点的最大路径和与1中的最大路径和的区别，搞清楚这一区别异常关键。用实例举例：我们现在操作当前结点20，显然15，20，7属于情况1，而15，20属于情况2、3，并且15,20会返回到父结点-10再做判断。
  另外，为了提高效率，我们发现负值对于求路径最大和是不利的，所以在求leftMax,rightMax,temp需要加一个判断，如果为负数，就果断舍弃。

代码

  1. 在这里插入代码片class Solution {
  2. public:
  3.     int maxPathSum(TreeNode* root) {
  4.         if(!root)
  5.             return 0;
  7.         helper(root);
  8.         return maxSum;
  9.     }
  11.     int helper(TreeNode* root){
  12.         if(!root)
  13.             return 0;
  14.         //1 属于后序遍历框架中对当前结点的操作，只需实时更新最大和即可
  15.         //2.3 含有回溯思想，由于遍历是自顶向下的过程，需要通过某种方式将当前结点的状态(当前结点+当前结点的左/右子树最大和)返回到其父结点
  16.         ////当前结点状态为负，抛弃
  17.         int leftMax = max(0, helper(root->left));        //获取当前结点左子树的最大路径和
  18.         int rightMax = max(0, helper(root->right));      //获取当前结点右子树的最大路径和
  19.         //获取以当前结点为父节点的最大路径和
  20.         maxSum = max(maxSum, root->val + leftMax + rightMax);
  21.         //获取经过当前结点且可以回到上一层的最大路径和  
  22.         int temp = max(0, max(leftMax, rightMax) + root->val);
  24.         return temp;      
  25.     }
  28. private:
  29.     int maxSum = INT_MIN;
  30. };

如果有错误或者不严谨的地方，请务必给予指正，十分感谢。