南京建设机械网站,山东省建设厅的网站,免费推广链接,企业线上推广公司【每日刷题】Day96 #x1f955;个人主页#xff1a;开敲#x1f349; #x1f525;所属专栏#xff1a;每日刷题#x1f34d; #x1f33c;文章目录#x1f33c;
1. LCP 44. 开幕式焰火 - 力扣#xff08;LeetCode#xff09;
2. 1022. 从根到叶的二进制数之和 - …【每日刷题】Day96 个人主页开敲 所属专栏每日刷题 文章目录
1. LCP 44. 开幕式焰火 - 力扣LeetCode
2. 1022. 从根到叶的二进制数之和 - 力扣LeetCode
3. 563. 二叉树的坡度 - 力扣LeetCode 1. LCP 44. 开幕式焰火 - 力扣LeetCode //思路记数递归。这个题目之前用C刷过现在用C复写一遍。 class Solution { public: void _numColor(TreeNode* root,int* hash,int ans) { //遍历到空返回 if(!root) return; //如果当前焰火颜色没有被记录过则焰火颜色种类1 if(!hash[root-val]) ans; //将遍历到的每一个焰火颜色记录防止重复 hash[root-val]1; _numColor(root-left,hash,ans); _numColor(root-right,hash,ans); } int numColor(TreeNode* root) { int ans 0; int hash[1001] {0}; _numColor(root,hash,ans); return ans; } }; 2. 1022. 从根到叶的二进制数之和 - 力扣LeetCode //思路递归模拟栈。 //题目要求我们将树的每一条分支看作一个二进制数字将所有分支的二进制数字的和返回。 //那么我们如何求得每一条分支的二进制数字呢 //首先我们想到的是采用先序遍历的方法去遍历每一条分支但是这里就有一个问题我们如何区分不同分支代表的二进制数字呢 //这里我们采用栈的数据结构来解决这个问题我们画图理解 //这里又会有一个问题当我们遍历完当前分支后如何将栈顶数据推出呢 //其实非常简单我们只需要利用形参的特性就行了看下面的实现代码。 class Solution { public: //判断是否为叶子节点 bool IsLeafNode(TreeNode* root) { return !root-left!root-right; } //注意到这里的count我用的是形参因为每次递归都会创建一个新的函数栈帧以存储当前的递归函数因此每一个count都是独一无二的比如上一层的count是1这一层的count是2当我们当前函数结束返回时会返回到上一层的函数使用上一层的count也就是1利用这个特性我们就能很好的实现不断更新栈顶数据。 void _sumRootToLeaf(TreeNode* root,int* Stack,int count,int ans) { //如果为空直接返回 if(!root) return; //不为空则将当前val入栈 Stack[count] root-val; //如果为叶子节点则开始计算 if(IsLeafNode(root)) { //次方 int flag 0; //从栈顶往栈底计算 for(int i count;i0;i--) { anspow(Stack[i]*2,flag); //特殊处理0^0 1 if(!Stack[i]!flag) ans-1; flag; } return; } //线序遍历 _sumRootToLeaf(root-left,Stack,count1,ans); _sumRootToLeaf(root-right,Stack,count1,ans); } int sumRootToLeaf(TreeNode* root) { int Stack[1001] {0}; int ans 0; _sumRootToLeaf(root,Stack,0,ans); return ans; } }; 3. 563. 二叉树的坡度 - 力扣LeetCode //思路先序遍历求和返回。 class Solution { public: int _findTilt(TreeNode* root,int ans) { //空节点坡度为0 if(!root) return 0; //计算左子树的和 int ret1 _findTilt(root-left,ans); //计算右子树的和 int ret2 _findTilt(root-right,ans); //求坡度并相加 ansabs(ret1-ret2); //返回左右子树的和当前节点的val return ret1ret2root-val; } int findTilt(TreeNode* root) { int ans 0; _findTilt(root,ans); return ans; } };
