请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果:[[3],[20,9],[15,7]]
=====================================================
相比32-II加了一个判断,判断是插在数组的前面还是后面
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> v; if (root == NULL) return v; queue<TreeNode *> q; q.push(root); int i = 0; while (!q.empty()) { q.push(NULL); TreeNode* r = q.front(); vector<int> t; while (r != NULL) { if (i % 2 == 0) t.push_back(r->val); else t.insert(t.begin(), r->val); if (r->left) q.push(r->left); if (r->right) q.push(r->right); q.pop(); r = q.front(); } q.pop(); if (t.size() != 0) { v.push_back(t); i++; } } return v; } };
看题解,这个题目貌似是想考察双端队列,但是没有什么必要性,其实是双端队列自己不怎么熟悉,又熟悉了一下,c++的deque不太好做,看到一个大神写的用双栈实现的类似双端丢列的写法,跪了
class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { if(root==NULL) return {}; stack<TreeNode*> s1; //管理第0层等偶数层 stack<TreeNode*> s2; // 管理第1层等奇数层 vector<vector<int>> res; s1.push(root); int count = 0; while(!s1.empty() || !s2.empty()){ vector<int> temp; if(count%2==0){ int len = s1.size(); for(int i=0;i<len;i++){ temp.push_back(s1.top()->val); if(s1.top()->left) s2.push(s1.top()->left); if(s1.top()->right) s2.push(s1.top()->right); s1.pop(); } } else{ int len = s2.size(); for(int i=0;i<len;i++){ temp.push_back(s2.top()->val); if(s2.top()->right) s1.push(s2.top()->right); if(s2.top()->left) s1.push(s2.top()->left); s2.pop(); } } count++; res.push_back(temp); } return res; } };