路徑總和Ⅲ

這題和和《為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;
}