题解 | #二叉树的之字形层序遍历#

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        // write code here
        vector<vector<int>> res;
        if(!root)
            return res;

        stack<TreeNode*> s1,s2;
        vector<int> vec;

        s1.push(root);

        while(!s1.empty() || !s2.empty()){
            while(!s1.empty()){
                TreeNode * node=s1.top();
                s1.pop();

                vec.push_back(node->val);

                if(node->left)
                    s2.push(node->left);
                if(node->right)
                    s2.push(node->right);

            }

            if(!vec.empty()){
                res.push_back(vec);
                vec.clear();
            }

            while(!s2.empty()){
                TreeNode * node=s2.top();
                s2.pop();

                vec.push_back(node->val);

                if(node->right)
                    s1.push(node->right);
                if(node->left)
                    s1.push(node->left);
            }

            if(!vec.empty()){
                res.push_back(vec);
                vec.clear();
            }
        }

        return res;

    }



};