124. Binary Tree Maximum Path Sum.md

124. Binary Tree Maximum Path Sum

思路

给定一棵二叉树，求最大路径和，路径的起始和结尾可以是任意节点。

这题的难点就在于起始点和结尾点都可以是任意节点，如果要求起始点就是根节点那就好做很多。我们设maxRootPathSum(root)代表以root为起始结点的路径最大和，那题目要求的maxPathSum(root)是候选值可能是多少呢？很简单，我们可以计算root左右两个子结点的maxRootPathSum，那么maxPathSum(root)就可能等于root->val + maxPathSum(root->left) + maxPathSum(root->right)。所以我们可以用一个类似后序遍历的递归函数来实现maxPathSum(root)，在这个递归函数中用一个全局变量res记录遇到的最大的maxPathSum。

总结：由于二叉树本来就是通过递归定义的，所以二叉树的题很多可以用递归来做，而且多数时候就是类似遍历一遍二叉树。

相当于就是后序遍历，所以复杂度为O(n)。

C++

class Solution {
private:
    int res = INT_MIN;
    int maxRootPathSum(TreeNode* root){
        /*
          以root为起始结点的路径最大和
        */
        if(!root) return 0;
        int l = max(maxRootPathSum(root -> left), 0);
        int r = max(maxRootPathSum(root -> right), 0);
        res = max(res, root -> val + l + r);
        return root -> val + max(l, r);
    }
public:
    int maxPathSum(TreeNode* root) {
        maxRootPathSum(root);
        return res;
    }
};