[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)，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int maxPathSum(TreeNode* root) {
	int res = INT_MIN;
	maxPath(root, res);
	return res;
	}
	private:
	//localMax[i] represents max half path end at node i, localMax[i] = max(localMax[i->left] + i->val, localMax[i->right] + i->val, i->val)
	int maxPath(TreeNode* root, int& res)
	{
	if(!root)return 0;
	int left = maxPath(root->left, res), right = maxPath(root->right, res);
	left = max(0, left);
	right = max(0, right);
	res = max(res, left + root->val + right);
	return max(left, right) + root->val;
	}
	};

view raw Binary Tree Maximum Path Sum.cpp hosted with ❤ by GitHub