[LeetCode]Path Sum III

相当于树的求区间和的问题，区间的定义就是自上而下的一条path，可以开始或者终结于内部，那么很明显我们又可以转化为presum的问题，时间复杂度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 pathSum(TreeNode* root, int sum) {
	unordered_map<int, int> map;
	map[0] = 1;
	int res = 0;
	maxPath(root, 0, sum, res, map);
	return res;
	}
	private:
	void maxPath(TreeNode* root, int preSum, int sum, int& count, unordered_map<int, int>& preSums)
	{
	if(!root)return;
	preSum += root->val;
	count += preSums[preSum - sum];
	++preSums[preSum];
	maxPath(root->left, preSum, sum, count, preSums);
	maxPath(root->right, preSum, sum, count, preSums);
	--preSums[preSum];
	}
	};

view raw Path Sum III.cpp hosted with ❤ by GitHub