美团开奖了，开的比要的还多。。。

精品推荐：

《征服数据结构》专栏：50多种数据结构彻底征服

《经典图论算法》专栏：50多种经典图论算法全部掌握

最近美团陆续开奖了，给的薪资大家还是比较满意的，很多网友也都晒出了自己的薪资，有的开的比要的还多，给hr说的期望薪资是27k，结果开了30k，这是要少了吗？

我印象中都很久没点外卖了，都快把它给卸载了，刚查了一下美团的市值，从9月份到10月份一路狂奔，市值翻了一倍，怪不得美团这次给的这么爽快。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第103题：二叉树的锯齿形层序遍历。

输入：root = [3,9,20,null,null,15,7]

输出：[[3],[20,9],[15,7]]

输入：root = [1]

输出：[[1]]

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null)
        return ans;
    Queue<TreeNode> queue = new LinkedList<>();// 创建队列
    queue.add(root);// 根节点添加到队列中
    boolean leftToRight = true;
    while (!queue.isEmpty()) {
        // 当前层的节点个数
        int count = queue.size();
        List<Integer> mList = new LinkedList<>();// 当前层的集合
        // 遍历这一行的所有节点
        for (int i = 0; i < count; i++) {
            TreeNode node = queue.poll();
            // 判断是从左往右打印还是从右往左打印。
            if (leftToRight) {// 从左往右添加到后面
                mList.add(node.val);
            } else {// 从右往左添加到前面
                mList.add(0, node.val);
            }
            // 左右子节点如果不为空会被加入到队列中
            if (node.left != null)
                queue.add(node.left);
            if (node.right != null)
                queue.add(node.right);
        }
        ans.add(mList);
        leftToRight = !leftToRight;// 下一步更改方向
    }
    return ans;
}

public:
    vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
        vector<vector<int>> ans;
        if (root == nullptr)
            return ans;
        queue<TreeNode *> nodeQueue;// 创建队列
        nodeQueue.push(root);// 根节点添加到队列中
        bool leftToRight = true;
        while (!nodeQueue.empty()) {
            // 当前层的节点个数
            int count = nodeQueue.size();
            deque<int> levelList;// 当前层的集合
            // 遍历这一行的所有节点
            for (int i = 0; i < count; i++) {
                TreeNode *node = nodeQueue.front();
                nodeQueue.pop();
                // 判断是从左往右打印还是从右往左打印。
                if (leftToRight) {// 从左往右添加到后面
                    levelList.push_back(node->val);
                } else {// 从右往左添加到前面
                    levelList.push_front(node->val);
                }
                // 左右子节点如果不为空会被加入到队列中
                if (node->left)
                    nodeQueue.push(node->left);
                if (node->right)
                    nodeQueue.push(node->right);
            }
            ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});
            leftToRight = !leftToRight;// 下一步更改方向
        }
        return ans;
    }

def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    ans = []
    if root is None:
        return ans
    q = deque([root])  # 创建队列,顺便把根节点添加到队列中
    leftToRight = True
    while q:
        mList = []  # 当前层的集合
        # 遍历这一行的所有节点
        for _ in range(len(q)):
            node = q.popleft()
            mList.append(node.val)
            # 左右子节点如果不为空会被加入到队列中
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        # 添加的时候注意方向
        ans.append(mList if leftToRight else mList[::-1])
        leftToRight = not leftToRight  # 下一步更改方向
    return ans