/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ //好蠢的写法啊 class Solution {public:    vector
     
      
       > zigzagLevelOrder(TreeNode* root) {        stack
       
         st;        vector
        
         
          > res;        vector
          
            first; if(root == NULL){ return res; } else{ first.push_back(root->val); res.push_back(first); } st.push(root); int flag = 0; while(!empty(st)){ vector
           
             tres; queue
            
              que; while(!empty(st)){ TreeNode* temp = st.top(); que.push(temp); st.pop(); } if(flag%2 == 0){ while(!empty(que)){ TreeNode* temp = que.front(); if(temp->right != NULL){ st.push(temp->right); tres.push_back(temp->right->val); } if(temp->left != NULL){ st.push(temp->left); tres.push_back(temp->left->val); } que.pop(); } } if(flag%2 == 1){ while(!empty(que)){ TreeNode* temp = que.front(); if(temp->left != NULL){ st.push(temp->left); tres.push_back(temp->left->val); } if(temp->right != NULL){ st.push(temp->right); tres.push_back(temp->right->val); } que.pop(); } } flag++; if(tres.size()) res.push_back(tres); } return res; }};
            
           
          
         
        
       
      
     

上面是把stack转移到一个queue中

下面是利用两个stack互转做

/** * Definition for binary tree * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    vector
     
      
        > zigzagLevelOrder(TreeNode *root) {        vector
       
        
          >res;        if (!root) return res;        stack
         
           s1;        stack
          
            s2; s1.push(root); vector
           
             out; while (!s1.empty() || !s2.empty()) { while (!s1.empty()) { TreeNode *cur = s1.top(); s1.pop(); out.push_back(cur->val); if (cur->left) s2.push(cur->left); if (cur->right) s2.push(cur->right); } if (!out.empty()) res.push_back(out); out.clear(); while (!s2.empty()) { TreeNode *cur = s2.top(); s2.pop(); out.push_back(cur->val); if (cur->right) s1.push(cur->right); if (cur->left) s1.push(cur->left); } if (!out.empty()) res.push_back(out); out.clear(); } return res; }};