題目要求

返回其節點值的鋸齒形層序遍歷（也就是，如果第一層遍歷順序時從左到右，第二次遍歷順序就要從右到左，依次類推）

圖解示例

算法思想

方法一：使用廣度優先搜索 + 調整結果

本題比較簡單的辦法就是先使用廣度優先搜索，即遍歷到哪一層，都按從左到右的順序放入列表中

完成遍歷后，對偶數層（即下標為單數的 ans[i]）的遍歷結果，倒轉順序

方法二：使用棧+列表

通過分析示例，我們發現，偶數層的遍歷順序與輸出順序剛好相反，即本來先遍歷到的數據，后出現在列表中

使用棧（先進后出）的方式存儲偶數層節點數據，當換到下一層的時候，依次 pop 出棧中的數據，放到分步

完整代碼

方法一：使用廣度優先搜索 + 調整結果

class Solution { public:vector<vector<int> > zigzagLevelOrder(TreeNode* root) {vector<vector<int> > ans;if(root==NULL) return ans;// 分步結果 vector<int> temp;// 層數標記 int flag_layer = 1;// 廣度優先搜索 queue<pair<TreeNode*, int> > q;q.push(make_pair(root,1));while(!q.empty()) {pair<TreeNode*, int> p = q.front();q.pop();// 記錄節點和層數TreeNode* node = p.first;int layer = p.second;// 下一層時，需要將分步結果temp中的數據放入ans中，并重置分步結果temp，用來存儲新一層的數據if(layer!=flag_layer) {ans.push_back(temp);temp.clear();flag_layer = layer;}temp.push_back(node->val);// 繼續廣度遍歷if(node->left) {q.push(make_pair(node->left,layer + 1));}if(node->right) {q.push(make_pair(node->right,layer+1));}int size = q.size();}// 最后一層的分步結果加入ansans.push_back(temp);// 將下標為奇數的ans中的對應表列表中的數據倒轉for(int i = 1; i < ans.size(); i+=2) {int len = ans[i].size();for(int j = 0; j < len/2; j++) {int temp = ans[i][j];ans[i][j] = ans[i][len-1-j];ans[i][len-1-j] = temp;}}return ans;} };

方法二：使用棧+列表

class Solution { public:vector<vector<int> > zigzagLevelOrder(TreeNode* root) {vector<vector<int> > ans;if(root==NULL) return ans;// 分步結果 vector<int> temp;// 記錄偶數層數據stack<int> even_stack;// 廣度優先搜索 queue<pair<TreeNode*, int> > q;//標記層數 int layer_flag = 1;q.push(make_pair(root,1));while(!q.empty()) {pair<TreeNode*, int> p = q.front();q.pop();TreeNode* node = p.first;int layer = p.second;// 下一層時，需要將分步結果temp/even_stack中的數據放入ans中，并重置分步結果temp/even_stack，// 用來存儲新一層的數據if(layer!=layer_flag) {while(!even_stack.empty()) {temp.push_back(even_stack.top());even_stack.pop();} ans.push_back(temp);temp.clear();layer_flag = layer; }// 判斷當前層需要用到哪一種數據結構存儲 if(layer%2==0) {even_stack.push(node->val);} else {temp.push_back(node->val);}// 繼續廣度遍歷if(node->left) {q.push(make_pair(node->left,layer + 1));}if(node->right) {q.push(make_pair(node->right,layer+1));}}// 最后一層的分步結果加入ansif(layer_flag%2==0) {while(!even_stack.empty()) {temp.push_back(even_stack.top());even_stack.pop();} ans.push_back(temp);} else{ans.push_back(temp);}return ans;} };

設計分析

方法一：

時間復雜度：O(n+(logn)²/2)~o(n)：n是指遍歷整棵樹，logn/2是指層數，logn指層數中的size

空間復雜度：O(2logn)~o(logn)需要一個隊列，和分步結果隊列

方法二：

時間復雜度：O(nlogn/2)：n是指遍歷整棵樹，logn/2是指需要使用棧的層數

空間復雜度：O(3logn)~o(logn)：需要一個隊列，和分步結果隊列，一個棧

提交結果

若有其他解法，歡迎評論區補充。

總結

以上是生活随笔為你收集整理的【LeetCode】0103.二叉树的锯齿形层序遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。