[数据结构与算法]LeetCode: 打印二叉树

低阶

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

一层更节省空间。

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        queue<TreeNode*> my_queue; //利用队列先进先出特性，广度搜索
        if(root != nullptr) my_queue.push(root);
        vector<int>res;
        while(!my_queue.empty()) 
        {
            if(my_queue.front()->left != nullptr) my_queue.push(my_queue.front()->left);
            if(my_queue.front()->right != nullptr) my_queue.push(my_queue.front()->right);
            res.push_back(my_queue.front()->val);
            my_queue.pop();
        }
        return res;
    }
};

中阶?

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

分层BFS：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> last;
        if (root != nullptr) last.push(root);
        while (!last.empty()) {
            vector<int> temp;
            queue<TreeNode*> next;
            while (!last.empty()) {
                if (last.front()->left != nullptr) next.push(last.front()->left);
                if (last.front()->right != nullptr) next.push(last.front()->right);
                temp.push_back(last.front()->val);
                last.pop();
            }
            last.swap(next);  // 基于move实现的，不涉及数据的拷贝
            res.emplace_back(temp);
        }
        return res;
    }
};

?递归：

class Solution {
public:
    vector<vector<int>> ans;

    vector<vector<int>> levelOrder(TreeNode* root) {
        write(root, 0);
        return ans;
    }

private:
    void write(TreeNode* root, int i) {
        if (root == nullptr) return;
        if (ans.size() == i) ans.push_back({});
        ans[i].push_back(root->val);
        write(root->left, i+1);
        write(root->right, i+1);
    }
};

高阶?

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

分层BFS：

利用deque可以两端插入和删除的特点。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        deque<TreeNode*> last;
        if (root != nullptr) last.push_back(root);
        
        bool fromLeft = true;
        while (!last.empty()) {
            vector<int> temp;
            deque<TreeNode*> next;
            while (!last.empty()) {
                TreeNode* theNode = nullptr;
                if (fromLeft) {
                    theNode = last.front();
                    last.pop_front();
                    if (theNode->left != nullptr) next.push_back(theNode->left);
                    if (theNode->right != nullptr) next.push_back(theNode->right);
                } else {
                    theNode = last.back();
                    last.pop_back();
                    if (theNode->right != nullptr) next.push_front(theNode->right);
                    if (theNode->left != nullptr) next.push_front(theNode->left);
                }
                temp.push_back(theNode->val);
            }
            fromLeft = !fromLeft;
            res.emplace_back(temp);
            last.swap(next);
        }
        return res;
    }
};

将中阶的奇数行 reverse，开发简单。