leetcode 103 Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes\' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \\
  9  20
    /  \\
   15   7

return its zigzag level order traversal as:

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

本题和102一样，都是层次遍历，但是在层次遍历的时候下一层需要进行反向。因此遍历每层的节点时，仍旧沿着左右的顺序进行遍历，正常情况下该层的元素直接压入尾部，但是需要反向的时候元素需插入头部。最开始考虑到是反向时遍历的顺序也进行反向，但是由于递归的情况，反向的过程中出现混乱，结果不对。最终代码记录如下：

/**
 * 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<vector<int>> zigzagLevelOrder(TreeNode* root) {
		vector<vector<int>> ret;
		if (!root)
		{
			return ret;
		}
		bfsZigzagLevelOrder(ret, 0, true, root);
		return ret;
	}

	void bfsZigzagLevelOrder(vector<vector<int>> &ret, int level, bool b_left, TreeNode* root)
	{
		if (!root)
		{
			return;
		}
		if (ret.size() == level)
		{
			ret.push_back({});
		}
        
        //Attension: why here ?
		if (b_left)
		{
			ret[level].push_back(root->val);
		}
		else
		{
			ret[level].insert(ret[level].begin(), root->val);
		}
		bfsZigzagLevelOrder(ret, level + 1, !b_left, root->left);
		bfsZigzagLevelOrder(ret, level + 1, !b_left, root->right);
	}
};