题意

对于给定的二叉树，计算经过节点值总和最大的路径的节点值总和。

思路

我们可以发现，对于某棵二叉树，其所有路径只有三种可能:

1. 路径全部位于左节点一侧
2. 路径全部位于右节点一侧
3. 路径包含根节点

因此，对于一颗给定的二叉树，我们可以将其递归处理，分别求出其左右子树节点值总和最大路径的和，最后就可以求出该二叉树的最大路径和，可以使用深度优先搜索的思想来构造计算函数。

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int k=-1919810;//将k初始化为一个足够小的值
    int dfs(TreeNode* P)
    {
        if(P == NULL) return -114514;//若P为空则返回一个负值表示
        int lMax,rMax;
        lMax=max(dfs(P->left),0);
        rMax=max(dfs(P->right),0);
        //分别对左右子树进行递归搜索
        k=max(k,P->val+lMax+rMax);
        return P->val+max(lMax,rMax);
    }
    int maxPathSum(TreeNode* root) 
    {
        // write code here
        dfs(root);
        return k;
    }
};

复杂度分析

时间复杂度：$O(n)O(n)$,$nn$是二叉树的节点个数，每个节点都至少遍历到了一次。

空间复杂度：$O(n)O(n)$,为深度优先搜索所用栈空间。