信誉好的做网站公司,云朵课堂网站开发怎么收费,微信广告代理,网站的安全性建设路径总和Ⅲ 这题和和《为K的数组》思路一致#xff0c;也是用前缀表。 代码调试过#xff0c;所以还加一部分用前序遍历数组和中序遍历数组构造二叉树的代码。
#includevector
#includeunordered_map
#includeiostream
using namespace std;
//Def…路径总和Ⅲ 这题和和《为K的数组》思路一致也是用前缀表。 代码调试过所以还加一部分用前序遍历数组和中序遍历数组构造二叉树的代码。
#includevector
#includeunordered_map
#includeiostream
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_maplong long, intmap;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(vectorint preorder, vectorint 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;}}vectorintleft_in(inorder.begin(), inorder.begin() index);vectorintright_in(inorder.begin() index 1, inorder.end());vectorintleft_pre(preorder.begin() 1, preorder.begin() 1 left_in.size());vectorintright_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(vectorint preorder, vectorint inorder) {return build(preorder, inorder);}
};int main()
{vectorintinorder {3,3,-2,5,2,1,10,-3,11};vectorintpreorder { 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;
}
