外链网站大全,脉脉用的什么技术做网站,墨星写作网站,wordpress 定制目录 一题目#xff1a;
二思路汇总#xff1a;
1.二叉树层序遍历#xff1a;
1.1题目介绍#xff1a;
1.2 解答代码#xff08;c版#xff09;#xff1a;
1.3 解答代码#xff08;c版#xff09;#xff1a;
1.4 小结一下#xff1a;
2.奇偶树分析#xf… 目录 一·题目
二·思路汇总
1.二叉树层序遍历
1.1题目介绍
1.2 解答代码c版
1.3 解答代码c版
1.4 小结一下
2.奇偶树分析
2.1 被leetcode强制否定的思路
2.2被迫转换的思路
三·解答代码 一·题目 leetcode链接 1609. 奇偶树 - 力扣LeetCode
二·思路汇总
1.二叉树层序遍历
1.1题目介绍
解答这道题其实首先可以说是和leetcode上的另一道题相关即二叉树的层序遍历 leetcode链接. - 力扣LeetCode
对这道题也就不过多解释了只是用到了这道题的相关代码可以说是奇偶树是基于这道题。
1.2 解答代码c版
//思路利用队列先进先出后进后出原则把树的节点放入每次取出队列第一个元素就把它的val按照顺序放入数组
//然后保存并pop掉放入左右孩子节点不为NULL由于是放入二维数组的每一行故利用for循环每次计算队列数据个数来控制
//最后注意每次放入二维数组每一行后既for完成一次换行。//接口函数要完成的任务1·返回层序遍历树得到的按规定的二维数组指针.2·改变并得到二维数组的总行数。3·改变对应的每行的列数typedef struct TreeNode *qdatatype;
typedef struct Qnode {struct Qnode* next;qdatatype data;
}Qnode;
typedef struct queue {int size;Qnode* head;Qnode* tail;
}queue;
void Queueinit(queue* p) {assert(p);p-head p-tail NULL;p-size 0;
}void Queuedestroy(queue* p) {assert(p);Qnode* cur p-head;while (cur) {Qnode* next cur-next;free(cur);cur next;}p-size 0;p-tail p-head NULL;
}
void Queuebackpush(queue* p, qdatatype x) {assert(p);Qnode* newnode (Qnode*)malloc(sizeof(Qnode));if (newnode NULL) {perror(malloc);return;}newnode-next NULL;newnode-data x;if (p-tail NULL) {p-head p-tail newnode;}else {p-tail-next newnode;p-tail newnode;}p-size;}
qdatatype Queuefrontdata(queue* p) {assert(p);assert(p-size 0);return p-head-data;
}
bool QueueEmpty(queue* p) {assert(p);return p-size 0;
}
void Queuefrontpop(queue* p) {assert(p);assert(p-size 0);if (p-head-next NULL) {free(p-head);p-head p-tail NULL;}else {Qnode* next p-head-next;free(p-head);p-head next;}p-size--;
}
int Queuesize(queue* p) {assert(p);return p-size;
}
//以上是开辟的队列int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {* returnSize0;int**pp(int**)calloc(2000,sizeof(int*));//利用二级指针来开辟二维数组首先开辟2000行可以理解为下面再利用每一行的首地址来开辟每一行的一维数组即列数if(rootNULL){return NULL;}//空树直接返回NULLqueue q;Queueinit(q);Queuebackpush(q, root);//先放入树的根节点int row0;//树的层数int count0;//每层树的节点的个数*returnColumnSizes (int*)malloc(sizeof(int) * 2000);//在外部传的是arr通过函数来改变数组内的数据故用二级指针接受//为每行开辟2000个空间while (!QueueEmpty(q)) {count Queuesize(q);//当pop掉上一行所有节点重新计算队列数据个数即下面要放入数组的每行的数据个数(*returnColumnSizes)[row]count;//记录每行列数pp[row](int*)calloc(count,sizeof(int));//放入数组得到每行的首地址在此开辟一维数组即二维数组每行的列数for(int i0;icount;i){struct TreeNode*retQueuefrontdata(q);pp[row][i]ret-val;Queuefrontpop(q);if (ret-left! NULL) {Queuebackpush(q, ret-left);}if (ret-right! NULL) {Queuebackpush(q, ret-right);}}//利用for循环将上一层节点所连的左右子节点放入满足队列内数据个数就是下一层的行的列数row;}Queuedestroy(q);*returnSizerow;return pp;}
1.3 解答代码c版
//思路把树的节点入队列每次队列数据入v后pop调之后拉进它的左右孩子入队队列的大小就是二维数组每行的数据数依次两个循环嵌套。
class Solution{
public:vectorvectorint levelOrder(TreeNode* root) {vectorintv;vectorvector intvv;queueTreeNode* q;if(rootNULL){return vv;}q.push(root);while(!q.empty()){int sizeq.size();int countsize;//记录每行大小也是push——back次数v.clear();//刷新v里面的数据while(count--){//vv[row].push_back(q.front()-val);因为一开始定义的vv没有开辟空间故不能这样用下标访问只有下面的push_back才//开了空间故可以直接插入数据。类似于用malloc给指针开辟空间再用下标访问而这里相当于用malloc故访问越界v.push_back(q.front()-val);TreeNode*tmpq.front();//保存节点指针方便后面pushq.pop();if(tmp-left!NULL){q.push(tmp-left);}if(tmp-right!NULL){q.push(tmp-right);}}vv.push_back(v);//每push完一层就加到vector后面。}return vv;}
};
1.4 小结一下
根据对于同一道题的解答代码长度和复杂度上明显c直接占极大优势感觉当初花很长时间的c代码直接让c代码瞬间秒杀而且难度也减小不亏是c的升级版感觉爱不释手了。
2.奇偶树分析
2.1 被leetcode强制否定的思路
先说一下一开始吧本以为如果先把它按照层序遍历到二维数组的话后面再对已知条件进行一次判断的话本来以为可以通过当看到测试用例过了 然而当提交的时候果然还是被leetcode给算计住了其实当看到val精确到10^6就觉得可能会来这一套说实话也没太出乎意料吧 这里用了简单hash表以及is_sorted() 等最后来判断是否符合不过这下子只能换思路咯
错误代码仅参考一下这个思路吧不过也pass掉咯
class Solution {
public:bool isEvenOddTree(TreeNode* root) {vectorintv;vectorvector intvv;queueTreeNode* q;if (root NULL) {return false;}q.push(root);while (!q.empty()) {int size q.size();int count size;//记录每行大小也是push——back次数v.clear();//刷新v里面的数据while (count--) {//vv[row].push_back(q.front()-val);因为一开始定义的vv没有开辟空间故不能这样用下标访问只有下面的push_back才//开了空间故可以直接插入数据。类似于用malloc给指针开辟空间再用下标访问而这里相当于用malloc故访问越界 v.push_back(q.front()-val);TreeNode* tmp q.front();//保存节点指针方便后面pushq.pop();if (tmp-left ! NULL) {q.push(tmp-left);}if (tmp-right ! NULL) {q.push(tmp-right);}}vv.push_back(v);//每push完一层就加到vector后面。}if(vv[0][0]%20){return false;}for(int i0;ivv.size();i){int hash[1000001]{0};for(int j0;jvv[i].size();j){if(i%20vv[i][j]%20){return false;}if(i%2!0vv[i][j]%2!0){return false;}if(hash[vv[i][j]]1){return false;}hash[vv[i][j]];}if(i%20){if(is_sorted(vv[i].begin(),vv[i].end(),lessint())){}else{return false;}}else{if(is_sorted(vv[i].begin(),vv[i].end(),greaterint())){}else{return false;}}}return true;}
}; 2.2被迫转换的思路
下面于是就想着可以在放入内部嵌套的vector 的过程中来判断是否符合。
由于把它依靠队列放入vector模拟的二维数组再判断奇偶层对应的奇偶数已经严格递增的话可能超过了时间限制故可以换个思路考虑当由队列放入v中就按照顺序筛选由于只要出现一种不符合条件的情况它就不是奇偶数故找到不合题意就直接给它false剩下的直接最后true就OK 筛选条件level要么是奇数要么是偶数为奇的话插入的数据应该是偶为偶的话插入的数据应该是奇否则直接false。 偶奇如果是第一个先直接插入但是也要有个比较v中的数据要小于要插入的才插入否则也直接false。 同理 奇偶也是如此如果是第一个先直接插入但是也要有个比较v中的数据要大要插入的才插入否则也直接false。 步骤总结 1.先模拟二叉树进入vector模拟的二维数组过程 2.进入vector的时候加上筛选条件
最后也是成功被leetcode放行通过了 尽管这种方法效率有点低吧 三·解答代码
class Solution {
public:bool isEvenOddTree(TreeNode* root) {vectorintv;vectorvector intvv;queueTreeNode* q;if (root NULL) {return false;}q.push(root);int row -1;while (!q.empty()) {int size q.size();row;//记录level的值int count size;//记录每行大小也是push——back次数v.clear();//刷新v里面的数据while (count--) {//vv[row].push_back(q.front()-val);因为一开始定义的vv没有开辟空间故不能这样用下标访问只有下面的push_back才//开了空间故可以直接插入数据。类似于用malloc给指针开辟空间再用下标访问而这里相当于用malloc故访问越界 if (row % 2 0 q.front()-val % 2 ! 0) {//判断为偶奇if (v.size() 0) {v.push_back(q.front()-val);}else if (v.end() find(v.begin(), v.end(), q.front()-val) v[v.size() - 1] q.front()-val){v.push_back(q.front()-val);//判断严格升序}else {return false;//非严格升序}}else if (row % 2 ! 0 q.front()-val % 2 0) {//判断为奇偶if (v.size() 0) {v.push_back(q.front()-val);}
else if (v.end() find(v.begin(), v.end(), q.front()-val) v[v.size() - 1] q.front()-val){v.push_back(q.front()-val);//判断严格降序}else {return false;//非严格降序}}else {//非-直接返falsereturn false;}TreeNode* tmp q.front();//保存节点指针方便后面pushq.pop();if (tmp-left ! nullptr) {q.push(tmp-left);}if (tmp-right ! nullptr) {q.push(tmp-right);}}vv.push_back(v);//每push完一层就加到vector后面。}return true;}
};
