【剑指Offer-32-II】从上到下打印二叉树 II

问题

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

示例

解答

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if (root) q.push(root);
        while (!q.empty()) {
            vector<int> ans;
            int s = q.size();
            for (int i = 0; i < s; i++) { // 每次只输出同一层的节点
                TreeNode* cur = q.front();
                q.pop();
                ans.push_back(cur->val);
                if (cur->left) q.push(cur->left);
                if (cur->right) q.push(cur->right);
            }
            res.push_back(ans);
        }
        return res;
    }
};

重点思路

与普通的层序遍历不同，本题要求将每层单独放在一个数组中，最后返回一个二维数组。刚开始碰到这题的时候，我第一时间想到的是之前用迭代做后序遍历，使用在数据节点后添加辅助节点对输出进行区别。所以当时在每个节点后加了一个层数节点，当层数变化时就重新生成一个数组，能做出来，但是与本题给出的算法相比效率就低了不少。

本题实际上只需要解决一个问题：如何每次只输出同批次的数据。在这里同批次的数据指的是同一层的节点。其实很简单，只需要事先提取该队列的size，然后只处理这个size中的数据即可。

【剑指Offer-32-II】从上到下打印二叉树 II

原文：https://www.cnblogs.com/tmpUser/p/14443726.html