用栈来做, 这一层先左后右入栈, 下一层先右后左入栈. 需要一个额外的中转栈.

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        stack<TreeNode *> st1;
        if (!root) return res;

        int dir = 1;
        st1.push(root);
        while (st1.size()) {
            int len = st1.size();
            vector<int> path;
            stack<TreeNode *> st2;

            while (len--) {
                TreeNode *p = st1.top();
                st1.pop();
                path.push_back(p->val);
                if (dir) {
                    if (p->left) st2.push(p->left);
                    if (p->right) st2.push(p->right);
                } else {
                    if (p->right) st2.push(p->right);
                    if (p->left) st2.push(p->left);
                }
            }
            res.push_back(path);
            dir = !dir;
            st1 = st2;
        }
        return res;
    }
};