這題是上一題的延伸
以為這題變化後要用BFS做
(如果要省時間的確要這樣)
因為看到discuss看到有人說 可以one queue without reversing….
害我想惹很久,結果點進去不出所料
還是有用其他空間(vector…)
如果用雙向的linkedlist做 才能達到省空間又省時間的作法吧
後來我就懶了 直接把奇數行reverse就好了 直接用algorithm的API幫你做好XD
class Solution { public: vector<vector<int>> ans; int level = 0; vector<vector<int>> zigzagLevelOrder(TreeNode* root) { if(root == NULL) return ans; else preorder(root); int len = ans.size(); for(int i = 1; i < len ; i += 2) { reverse(ans[i].begin(),ans[i].end()); } return ans; } void preorder(TreeNode* node) { if(node == NULL) return; level++; if(ans.size() < level) ans.push_back(vector<int>()); ans[level-1].push_back(node->val); preorder(node->left); preorder(node->right); level--; } };