剑指 Offer 32 - III. 从上到下打印二叉树 III

题目内容

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

例如:

1
2
3
4
5
6
7
8
9

给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
```           
返回其层次遍历结果：

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

1
2

提示：

节点总数 <= 1000

1
2
3
4
5

- - -

### 解法一：广度优先搜索

class Solution {
public:
vector<vector> levelOrder(TreeNode* root) {
if(!root) return {};
vector<vector> res;
queue<TreeNode*> que;
que.push(root);

    bool isOrderLeft = true;
    while(!que.empty()){
        deque<int> temp;

        int s=que.size();
        for(int i=0;i<s;i++){
            TreeNode *node = que.front();
            que.pop();
            
            if (isOrderLeft) temp.push_back(node->val);
            else temp.push_front(node->val);
            
            if(node->left)que.push(node->left);
            if(node->right)que.push(node->right);
        }
        res.emplace_back(vector<int>{temp.begin(), temp.end()});
        isOrderLeft = !isOrderLeft;
    }
    return res;
}

};

1
2
3

结果：

行用时：
4 ms
, 在所有 C++ 提交中击败了
71.00%
的用户
内存消耗：
13.3 MB
, 在所有 C++ 提交中击败了
5.05%
的用户
通过测试用例：
34 / 34
```