企业官网建设流程全解析

百色住房和城乡建设部网站,棋牌游戏在哪做网站,原创网站设计费用,wordpress主页面题目描述给你二叉树的根节点 root #xff0c;返回其节点值的 锯齿形层序遍历 。#xff08;即先从左往右#xff0c;再从右往左进行下一层遍历#xff0c;以此类推#xff0c;层与层之间交替进行#xff09;。示例 1#xff1a;输入#xff1a;root [3,9,20,null,nul…题目描述给你二叉树的根节点root返回其节点值的锯齿形层序遍历。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。示例 1输入root [3,9,20,null,null,15,7]输出[[3],[20,9],[15,7]]示例 2输入root [1]输出[[1]]示例 3输入root []输出[]提示树中节点数目在范围[0, 2000]内-100 Node.val 100解决方案这段代码的核心功能是实现二叉树的锯齿形层序遍历之字形遍历即第一层从左到右第二层从右到左第三层再从左到右以此类推交替遍历在普通层序遍历的基础上增加了 “偶数层反转结果” 的逻辑时间复杂度O(n)n为节点数空间复杂度O(n)是该问题的经典迭代解法。核心逻辑代码在普通层序遍历双数组模拟 BFS的基础上通过一个布尔标记控制 “是否反转当前层节点值数组”实现锯齿形效果边界处理若根节点为空直接返回空数组初始化容器与标记保留普通层序遍历的ans最终结果、cur当前层节点、nxt下一层节点、value当前层节点值新增布尔变量even初始为false标记当前层是否为 “需要反转的偶数层”第一层不反转第二层反转以此类推逐层遍历循环与普通层序遍历一致遍历当前层节点收集值到value并按左→右顺序收集下一层节点到nxt核心新增逻辑若even为true当前是偶数层调用reverse反转value数组实现从右到左的遍历效果将处理后的value加入ans更新cur为下一层节点并翻转even的值切换下一层的遍历方向返回结果遍历完成后ans中按锯齿形存储了各层节点值直接返回即可。总结核心思路在普通层序遍历的基础上通过布尔标记 数组反转实现锯齿形无需改变节点遍历顺序仅调整结果数组的顺序逻辑简洁关键细节even初始为false第一层不反转每遍历完一层就翻转even保证奇偶层交替反转效率特点整体时间O(n)反转操作的总时间为O(n)所有节点仅遍历一次空间开销与普通层序遍历一致是最优解法之一。函数源码/** * 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: vectorvectorint zigzagLevelOrder(TreeNode* root) { if(!root) return {}; vectorvectorintans{}; vectorTreeNode*cur{root}; vectorTreeNode*nxt{}; vectorintvalue{}; bool evenfalse; while(!cur.empty()){ value{}; nxt{}; for(auto i:cur){ value.push_back(i-val); if(i-left) nxt.push_back(i-left); if(i-right)nxt.push_back(i-right); } if(even) reverse(value.begin(),value.end()); ans.push_back(value); curnxt; even!even; } return ans; } };