二叉树Z形层序遍历

题目描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

解法

 vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr) {
            return ans;
        }
        queue<TreeNode*> que;
        que.push(root);
        bool isOrderLeft = true;
        while (!que.empty()) {
            int levelSize = que.size();
            list<int> levelList;
            for (int i = 0; i < levelSize; i++) {
                TreeNode* curNode = que.front();
                que.pop();
                // Z形
                if (isOrderLeft) {
                    levelList.push_back(curNode->val);
                } else {
                    levelList.push_front(curNode->val);
                }

                // 层序
                if (curNode->left) que.push(curNode->left);
                if (curNode->right) que.push(curNode->right);
            }
            vector<int> levelVec(levelList.begin(), levelList.end());
            ans.push_back(levelVec);
            // Z形: 方向一层一变换
            isOrderLeft = !isOrderLeft;
        }
        return ans;
    }