[LeetCode]Binary Tree Maximum Path Sum

就是Max Subarray和树形DP的结合，当然这道题树已经建好了我们就不需要考虑树形DP中麻烦的建树问题。我们每次去当前node n的左子树和右子树中寻找和最大的以n结尾的path，用localMax[n]表示，我们有递推公式：

• localMax[n] = max(localMax[n->left] + n->val, localMax[n->right] + n ->val, n->val)

根据左子树和右子树分别return回来的path，我们不断更新最大的Path Sum，时间复杂度O(n)，代码如下：