刷题之路径总和Ⅲ（leetcode）
路径总和Ⅲ
这题和和《为K的数组》思路一致，也是用前缀表。
代码调试过，所以还加一部分用前序遍历数组和中序遍历数组构造二叉树的代码。
#include<vector>
#include<unordered_map>
#include<iostream>
using namespace std;
//Definition for a binary tree node.
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
private:unordered_map<long long, int>map;int dfs(TreeNode* root, long long cur, int targetSum){if (root == NULL){return 0;}int count = 0;cur += root->val;if (map.find(cur - targetSum) != map.end()){count += map[cur - targetSum];}map[cur]++;int leftcount = dfs(root->left, cur, targetSum);int rightcount = dfs(root->right, cur, targetSum);map[cur]--;//因为路径总和只是针对同一个头结点，所以不是同一个头结点时需要回溯return count + leftcount + rightcount;}
public:int pathSum(TreeNode* root, int targetSum) {map[0] = 1;return dfs(root, 0, targetSum);}
};class tree {
private:TreeNode* build(vector<int>& preorder, vector<int>& inorder){if (preorder.size() == 0)return NULL;//找到根节点int rootvalue = preorder[0];TreeNode* root = new TreeNode(rootvalue);//叶子节点if (preorder.size() == 1)return root;//区分左右子树位置int index = 0;for (int i = 0; i < inorder.size(); i++){if (inorder[i] == rootvalue){index = i;break;}}vector<int>left_in(inorder.begin(), inorder.begin() + index);vector<int>right_in(inorder.begin() + index + 1, inorder.end());vector<int>left_pre(preorder.begin() + 1, preorder.begin() + 1 + left_in.size());vector<int>right_pre(preorder.begin() + 1 + left_in.size(), preorder.end());root->left = build(left_pre, left_in);root->right = build(right_pre, right_in);return root;}
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return build(preorder, inorder);}
};int main()
{vector<int>inorder = {3,3,-2,5,2,1,10,-3,11};vector<int>preorder = { 10,5,3,3,-2,2,1,-3,11 };int targetsum = 8;tree mytree;TreeNode* root = mytree.buildTree(preorder,inorder);Solution solution;int result = solution.pathSum(root, targetsum);cout << result << endl;
}