vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
auto ret = vector<vector<int>>();
zigzagLevelOrder(root, 0, ret);
void zigzagLevelOrder(const TreeNode* root, int level, vector<vector<int>>& ret) {
if (root == nullptr || level < 0) return;
if (ret.size() <= level) {
ret.push_back(vector<int>());
if (level % 2 == 0) ret[level].push_back(root->val);
else ret[level].insert(ret[level].begin(), root->val);
zigzagLevelOrder(root->left, level + 1, ret);
zigzagLevelOrder(root->right, level + 1, ret);