PROBLEM

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

难度 中等

MY ANSWER

使用双端队列deque进行bfs，奇数层正序遍历deque，偶数层倒序遍历deque。时间复杂度O(n)，空间复杂度O(n)。

/**
 * 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) {
        deque<TreeNode*> bfs;
        vector<vector<int>> res;
        bfs.push_back(root);
        int i = 1;
        while(bfs.size()) {
            vector<int> tmp;
            int s = bfs.size();
            if(i & 1) {
                for(int i = 0; i < s; i++) {
                    TreeNode* node = bfs.front();
                    if(node) {
                        tmp.push_back(node->val);
                        bfs.push_back(node->left);
                        bfs.push_back(node->right);
                    }
                    bfs.pop_front();
                }
            }
            else {
                for(int i = 0; i < s; i++) {
                    TreeNode* node = bfs.back();
                    if(node) {
                        tmp.push_back(node->val);
                        bfs.push_front(node->right);
                        bfs.push_front(node->left);
                    }
                    bfs.pop_back();
                }
            }
            i++;
            if(tmp.size()) {
                res.push_back(tmp);
            }
        }
        return res;
    }
};

BETTER ANSWER

使用队列进行bfs，偶数层调用reverse反转。时间空间复杂度同上。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        deque<TreeNode*> bfs;
        vector<vector<int>> res;
        bfs.push_back(root);
        while(bfs.size()) {
            vector<int> tmp;
            for(int i = bfs.size(); i > 0; i--) {
                TreeNode* node = bfs.front();
                if(node) {
                    tmp.push_back(node->val);
                    bfs.push_back(node->left);
                    bfs.push_back(node->right);
                }
                bfs.pop_front();
            }
            if(tmp.size()) {
                if(res.size() & 1) {
                    reverse(tmp.begin(), tmp.end());
                }
                res.push_back(tmp);
            }
        }
        return res;
    }
};

SUMMARY

  • 学习使用双端队列deque；
  • <algorithm>库里的：reverse(tmp.begin(), tmp.end())反转向量。