103. 二叉树的锯齿形层次遍历

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

3

/
9 20
/
15 7
返回锯齿形层次遍历如下：

[
[3],
[20,9],
[15,7]
]

思路
1.需要一个变量flag标示打印方向(从左到右还是从右到左)
2.使用一个变量numOfChild标示这一层有多少个节点

#include "TreeNode.h"

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        deque<TreeNode*> que;
        int flag = 0, numOfChild = 1;
        if (root == NULL) return result;
        que.push_back(root);

        while (!que.empty())
        {
            vector<int> temp;
            for (int i = 0; i < numOfChild; i++)
            {
                TreeNode* node;
                if (flag % 2 == 0)
                {
                    node = que.back();
                    que.pop_back();
                    if (node->left != NULL) que.push_front(node->left);
                    if (node->right != NULL) que.push_front(node->right);
                }
                else
                {
                    node = que.front();
                    que.pop_front();
                    if (node->right != NULL) que.push_back(node->right);
                    if (node->left != NULL) que.push_back(node->left);
                }
                temp.push_back(node->val);
            }
            flag++;
            numOfChild = que.size();
            result.push_back(temp);
        }
        return result;
    }
};

int main(int argc, char* argv[])
{
    string test = "3,9,20,null,null,15,7";
    auto tree = stringToTreeNode(test);
    auto res = Solution().zigzagLevelOrder(tree);
    return 0;
}