题解 | #二叉树的最大路径和#

题目：二叉树的最大路径和

描述：给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。这个路径的开始节点和结束节点可以是二叉树中的任意节点。

示例1：输入：{-2,1}，返回值：1。

解法一：

思路分析：在该题目中可以使用递归的方法去解决问题，设置最大值为max，即时更新，时刻返回的是左节点，右节点，0中的最大值，代表路径包括左节点，右节点，以及路径在此停止。max更新就是考虑所有情况，每次递归返回不需要考虑左右+val的值，因为已经确保路径跑到当前节点的父节点，返回值就是经过该结点的最大路径部分值。

举例说明：输入: [-10,9,20,null,null,15,7]

其中最大值为20 + 15 + 7 = 42。首先当遍历到第一层的时候，max的值设为-10，返回左节点的值9，右节点的值20，所以此时最大值max更新为20，依次更新左右结点，最后返回结点最大值为20。

当输入: [1,2,3]

输出最大值为1 + 2 + 3 = 6。

故具体C++代码为：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int maxl=-100000;
    int maxPathSum(TreeNode* root) {
        maxmid(root);//调用maxmid函数
        return maxl;
    }    
    int maxmid(TreeNode* root){
        if(root==NULL) //特殊情况
            return 0;
        int i=maxmid(root->left);
        int j=maxmid(root->right);
        int t=minmax({i,j,0}).second+root->val;//minmax返回最大最小值
        maxl=minmax({t,maxl,i+j+root->val,root->val}).second;//second是迭代器指向对应的值
        return t;
    }
};

因为要遍历每一个结点的值，故时间复杂度为O(N)，没有占用额外的内存空间，所以其空间复杂度为O(1)。

解法二：

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

以A为根节点的这棵树的最大路径和可能存在于哪里：

单纯的存在于以B为根节点的子树中，单纯的存在于以C为根节点的子树中，A节点到达左子树B中某节点的路径，A节点到达右子树C中某节点的路径，左子树B中某节点到达右子树C中某节点的路径，必然经过A节点(假如左、右子树的最大路径均为负数)，因为需要获得从A节点到达其子树中某节点的路径和，所以我们想到深度优先遍历。又因为计算以A为根节点的树的最大路径和计算其子树B、C中的最大路径和函数功能相同，所以同样采用递归算法。

其具体python代码如下所示：

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
#
#
# @param root TreeNode类
# @return int整型
#
class Solution:
    def maxPathSum(self , root ):
        # write code here
        def dfs(root):
            nonlocal maxval
            if not root:
                return float('-inf')
            #计算左右子树的最大单边路径
            left = dfs(root.left)
            right = dfs(root.right)
            #更新maxval
            maxval = max(maxval, left + root.val + right, left, right)#与历史最大值做比较
            return max(left + root.val, right + root.val, root.val)
           
        maxval = float("-inf")#表示负无穷
        return max(dfs(root), maxval)

也采用遍历算法，故时间复杂度为O(N)，没有占用额外的内存空间，所以其空间复杂度为O(1)。