辽宁省住房和城乡建设厅网站,专业网站建设方案,网站标签怎么做,注册公司名称查询网站1. 题目
给定一个二叉树#xff0c;返回其节点值的锯齿形层次遍历。#xff08;即先从左往右#xff0c;再从右往左进行下一层遍历#xff0c;以此类推#xff0c;层与层之间交替进行#xff09;。
例如#xff1a;
给定二叉树 [3,9,20,null,null,15,7],3/ \9 20/ \…1. 题目
给定一个二叉树返回其节点值的锯齿形层次遍历。即先从左往右再从右往左进行下一层遍历以此类推层与层之间交替进行。
例如
给定二叉树 [3,9,20,null,null,15,7],3/ \9 20/ \15 7
返回锯齿形层次遍历如下[[3],[20,9],[15,7]
]来源力扣LeetCode 链接https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 BFS队列反转
class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) {if(root NULL)return {};queueTreeNode* q;TreeNode *tp;q.push(root);vectorint lv;vectorvectorint ans;int n, depth 0;while(!q.empty()){n q.size();while(n--){tp q.front();q.pop();lv.push_back(tp-val); if(tp-left)q.push(tp-left);if(tp-right)q.push(tp-right);}depth;if(depth%2 0)//对相应的层进行反转reverse(lv.begin(),lv.end());ans.push_back(lv);lv.clear();}return ans;}
};2.2 双栈解题
奇偶层分别存在不同的栈里某个栈里的数据先入栈右节点
class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) {if(root NULL)return {};stackTreeNode* l, r;TreeNode *tp;l.push(root);vectorint lv;vectorvectorint ans;while(!l.empty() || !r.empty()){while(!l.empty()){tp l.top();l.pop();lv.push_back(tp-val); if(tp-left)r.push(tp-left);if(tp-right)r.push(tp-right);}if(!lv.empty()){ans.push_back(lv);lv.clear();}while(!r.empty()){tp r.top();r.pop();lv.push_back(tp-val);if(tp-right)l.push(tp-right);if(tp-left)l.push(tp-left); }if(!lv.empty()){ans.push_back(lv);lv.clear();} }return ans;}
};2.3 双端队列
class Solution {
public:vectorvectorint zigzagLevelOrder(TreeNode* root) {if(root NULL)return {};queueTreeNode* q;TreeNode *tp;q.push(root);dequeint lv;vectorvectorint ans;int n, depth 0;while(!q.empty()){n q.size();while(n--){tp q.front();q.pop();if(depth%2 0)lv.push_back(tp-val);elselv.push_front(tp-val);if(tp-left)q.push(tp-left);if(tp-right)q.push(tp-right);}depth;ans.push_back(vectorint(lv.begin(),lv.end()));lv.clear();}return ans;}
};
