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

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

解决方案：
稍微修改一下层次遍历，每次先将右子树入队，后将左子树入队，就能得到反向层次遍历的结果。
对相应深度的结果reverse一下即可。

vector<vector<int>> res;
    queue<pair<TreeNode*,int>> myQueue;
    myQueue.push({root,1});
    int lastDepth = 0;

    while (!myQueue.empty())
    {
        TreeNode*pos = myQueue.front().first; 
        int depth = myQueue.front().second;//当前结点深度
        myQueue.pop();  
        if (pos == NULL)
            continue;

        if (depth > lastDepth) //如果出现更深的结点，建立一个vector存储本层的结点值
        {
            res.push_back(vector<int>());
            lastDepth = depth;
        }
        res[depth - 1].push_back(pos->val); //存储

        /*先右后左*/
        if (pos->right != NULL)
            myQueue.push({ pos->right,depth + 1 });
        if (pos->left != NULL)
            myQueue.push({ pos->left,depth + 1 });

    }
    for (int i = 0; i < res.size(); i++)
        if (i % 2 == 0)  //按题目要求隔层对结果反序
        //vector方法：返回一个指向位置i的元素引用，该方法将自动检测i是否是在一个有效的范围，如果不是则将抛出out_of_range异常。
            reverse(res.at(i).begin(), res.at(i).end());
    return res;