面试题 32：从上到下打印二叉树.md

（1）试题链接：43. 不分行从上往下打印二叉树 - AcWing题库

方法一：层序遍历

• 思路：层序遍历模板题。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    vector<int> printFromTopToBottom(TreeNode* root) {
        if (!root) return {};
        
        vector<int> ans;
        queue<TreeNode*> q;
        q.emplace(root);
        
        while (!q.empty()) {
            auto node = q.front(); q.pop();
            ans.push_back(node->val);
            
            if (node->left) q.emplace(node->left);
            if (node->right) q.emplace(node->right);
        }
        
        return ans;
    }
};

（2）试题链接：44. 分行从上往下打印二叉树 - AcWing题库

方法一：层序遍历

• 思路：与上面的不同之处是每次把当前层级的所有元素的取出来。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        if (!root) return {};
        
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.emplace(root);
        
        while (!q.empty()) {
            int n = q.size();
            
            vector<int> tmp;
            tmp.reserve(n);
            
            for (int i = 0; i < n; i++) {
                auto node = q.front(); q.pop();
                tmp.push_back(node->val);
                
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
            
            ans.emplace_back(move(tmp));
        }
        
        return ans;
    }
};

（3）试题链接：45. 之字形打印二叉树 - AcWing题库

方法一：层序遍历

• 思路：奇数层反转一下即可。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    vector<vector<int>> printFromTopToBottom(TreeNode* root) {
        if (!root) return {};
        
        vector<vector<int>> ans;
        queue<TreeNode*> q;
        q.emplace(root);
        
        while (!q.empty()) {
            int n = q.size();
            
            vector<int> tmp;
            tmp.reserve(n);
            
            for (int i = 0; i < n; i++) {
                auto node = q.front(); q.pop();
                tmp.push_back(node->val);
                
                if (node->left) q.emplace(node->left);
                if (node->right) q.emplace(node->right);
            }
            
            if (ans.size() % 2) reverse(tmp.begin(), tmp.end());
            
            ans.emplace_back(move(tmp));
        }
        
        return ans;
    }
};