网站开发怎么报价单,项目免费推广平台,做网站怎么实现在线支付,做粉丝网站文章目录 一、LeetCode#xff1a;199. 二叉树的右视图二、LeetCode#xff1a;437. 路径总和 III 一、LeetCode#xff1a;199. 二叉树的右视图
LeetCode#xff1a;199. 二叉树的右视图 差点因为是个中等题打退堂鼓。其实比较简单。 右视图实际上只需要找到#xff0c… 文章目录 一、LeetCode199. 二叉树的右视图二、LeetCode437. 路径总和 III 一、LeetCode199. 二叉树的右视图
LeetCode199. 二叉树的右视图 差点因为是个中等题打退堂鼓。其实比较简单。 右视图实际上只需要找到每一层的最右边的那个结点即可。 dfs
确保每次找到底层最右边的结点时间复杂度 O ( n ) O(n) O(n)
class Solution {
public:vectorint rightSideView(TreeNode* root) {cur_floor 0;rightNode(root,0);return ans;}
private:void rightNode(TreeNode * root,int floor){//找到当前层最靠右的结点if(!root) return;if(floor cur_floor){ans.emplace_back(root-val);cur_floor;}rightNode(root-right,floor 1);rightNode(root-left, floor 1);return;}int cur_floor;vectorint ans;
};实际上使用层序遍历更好理解每次选择一层的最后一个节点就行 二、LeetCode437. 路径总和 III
LeetCode437. 路径总和 III 这个问题使用dfs可以解决不过实现起来比较复杂时间复杂度是 O ( n 2 ) O(n^2) O(n2)。我们先考虑其他方法。
发现使用树上前缀和很容易解决最坏时间复杂度也是 O ( n 2 ) O(n^2) O(n2)所以我们先考虑使用前缀和。 未优化的前缀和dfs回溯
最坏时间复杂度是 O ( n 2 ) O(n^2) O(n2)前缀和求和需要考虑元素大小的问题所以要使用long long对于每一个结点需要求其前缀和以及以当前结点结尾的序列的值的总和是否存在等于targetSum的向下递归左右子节点向上回溯。 class Solution {
public:int pathSum(TreeNode* root, int targetSum) {if(!root) return 0;vectorlong long presum;presum.emplace_back(0);//导入前导0getNum(root,targetSum,presum);return Num;}
private:void getNum(TreeNode * root,int targetSum,vectorlong long presum){if(!root) return;//压入当前值的前缀和presum.emplace_back(root-val presum.back());//判断以当前结点结尾的序列是否存在targetSum由于存在负值因此无法提前breakfor(int i presum.size() - 2;i 0;--i){if(presum.back() - presum.at(i) targetSum){Num;}}//继续向下递归getNum(root-left,targetSum,presum);getNum(root-right,targetSum,presum);//弹出当前值回溯presum.pop_back();return;}int Num0;
};做过两数之和之后很容易想到使用哈希表直接查找使用存在所需要的值。 p r e s u m 1 − p r e s u m 2 t a r g e t S u m presum1 - presum2 targetSum presum1−presum2targetSum则 p r e s u m 2 p r e s u m 1 − t a r g e t S u m presum2 presum1 - targetSum presum2presum1−targetSum
我们真的是需要哈希表找到需要的值吗在这里我们只需要之前有多少个这样的值就行了 因此哈希的key 目标前缀和,value 目标前缀和的个数
使用哈希优化的前缀和dfs回溯
哈希查找每个结点查找一次平均时间复杂度 O ( 1 ) O(1) O(1)整个时间复杂度为 O ( n ) O(n) O(n)使用std::unordered_map的count方法返回值是0或1表示存在或不存在。必须先判断是否存在所需前缀和再压入当前值。 原因是当前值和所需前缀和可能刚好相等导致当前前缀和也变成了答案的一部分但实际上它不能是答案的一部分相当于之前所说的是同一个前缀和了这使得序列为空。 class Solution {
public:int pathSum(TreeNode* root, int target) {if(!root) return 0;targetSum target;presum_num[0] 1;//导入前导0getNum(root,0);return Num;}
private:void getNum(TreeNode * root,long long presum){if(!root) return;long long cur_presum presum root-val;//判断以当前结点结尾的序列是否存在targetSumif(presum_num.count(cur_presum - targetSum) ! 0)Num presum_num[cur_presum - targetSum];//压入当前值的前缀和presum_num[cur_presum];//继续向下递归getNum(root-left,cur_presum);getNum(root-right,cur_presum);//弹出当前值回溯if(presum_num[cur_presum] ! 1) presum_num[cur_presum]--;else presum_num.erase(cur_presum);return;}int Num0;int targetSum;unordered_maplong long,int presum_num;
};前缀和的方法如果之前接触过很容易想到不过这里建议学习深度优先遍历的方法更深入理解dfs。 dfs
时间复杂度 O ( n 2 ) O(n^2) O(n2)实现两个递归函数 第一个函数dfs以根结点开始向下求和得到targetSum则Num第二个函数getNum遍历所有树节点每个结点调用dfs函数。 class Solution {
public:int pathSum(TreeNode* root, int target) {targetSum target;getNum(root);return Num;}
private:void getNum(TreeNode * root){if(!root) return;dfs(root,0);//包含本结点向下递归getNum(root-left);getNum(root-right);return;}void dfs(TreeNode * root,long long sum){if(!root) return;if(root-val sum targetSum) Num;dfs(root-left,sum root-val);dfs(root-right,sum root-val);return;}int Num 0;int targetSum;
};
