剑指 Offer 32 - III. 从上到下打印二叉树 III（双端队列deque）

原题

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

思路

我的思路：由剑指 Offer 32 - II. 从上到下打印二叉树 II可以容易想到每次遍历一层后存下的tmp数组，用一个bool变量来判断从左到右还是从右到左，进行翻转

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if (!root) return ans;
        queue<TreeNode*> q;
        q.push(root);
        bool left = true;
        while (!q.empty()) {
            vector<int> tmp;
            int num = q.size();
            while (num--) {
                TreeNode* top = q.front();
                q.pop();
                if (top->left) q.push(top->left);
                if (top->right) q.push(top->right);
                tmp.push_back(top->val);
            }
            if (!left){
                reverse(tmp.begin(), tmp.end());
            } 
            left = (left == true ? false: true);
            ans.push_back(tmp);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

运行截图

收获

对官方解的思考：

1. bool变量的翻转 isOrderLeft = !isOrderLeft
2. 顺序会变的序列可以用双端队列
   双端队列其实就是队列的变形，使用时需要加上< deque >头文件。
   特殊的函数使用：
   push_back()：在队列尾部添加元素
   push_front()：在队列头部添加元素
   pop_back()：删除队列尾部的元素
   pop_front()：删除队列头部的元素
   front() ：获得队列头部元素。
   back()： 获得队列尾部元素。