做ppt好的网站,加强网站的建设与管理,网站建设方案行业,app拉新怎么做437. 路径总和 III - 力扣#xff08;LeetCode#xff09;
前序遍历时#xff0c;维护当前路径#xff08;根节点开始#xff09;的路径和#xff0c;同时记录路径上每个节点的路径和 假设当前路径和为cur#xff0c;那么ans 路径和(cur - target)的出现次数
/*** D…437. 路径总和 III - 力扣LeetCode
前序遍历时维护当前路径根节点开始的路径和同时记录路径上每个节点的路径和 假设当前路径和为cur那么ans 路径和(cur - target)的出现次数
/*** 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 {
public:unordered_maplong long, int mp;long long ans 0;long long t;void dfs(TreeNode *root, long long cur) {if (root nullptr) return;cur root-val;ans mp[cur - t] ;mp[cur] ;dfs(root-left, cur);dfs(root-right, cur);mp[cur] -- ;cur - root-val;}int pathSum(TreeNode* root, int targetSum) {mp[0] ;t targetSum;long long cur 0;dfs(root, cur);return ans;}
};105. 从前序与中序遍历序列构造二叉树 - 力扣LeetCode
递归构造每次构造子树的根节点 根节点的左右子节点如何构造根据中序遍历中根节点的位置确定左右子树节点数量 在前序遍历中分别确定左右子树节点的范围两者的第一个节点就是根节点的左右节点
/*** 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 {
public:unordered_mapint, int mp;TreeNode* dfs(vectorint preorder, vectorint inorder, int l, int r, int ll, int rr) {if (l r) return nullptr;TreeNode *root new TreeNode(preorder[l]);int iidx mp[preorder[l]];int sz iidx - ll;root-left dfs(preorder, inorder, l 1, l sz, ll, iidx - 1);root-right dfs(preorder, inorder, l sz 1, r, iidx 1, rr);return root;}TreeNode* buildTree(vectorint preorder, vectorint inorder) {int n preorder.size();for (int i 0; i inorder.size(); i)mp[inorder[i]] i;return dfs(preorder, inorder, 0, n - 1, 0, n - 1);}
};
