剑指 Offer（第2版）面试题 32：从上到下打印二叉树

题目 1：不分行从上往下打印二叉树

题目来源：43. 不分行从上往下打印二叉树

层序遍历。

我们从根节点开始按宽度优先的顺序遍历整棵树，每次先扩展左儿子，再扩展右儿子。

这样我们会：

1. 先扩展根节点；
2. 再依次扩展根节点的左右儿子，也就是从左到右扩展第二层节点；
3. 再依次从左到右扩展第三层节点；
4. 依次类推…

代码：

/*** 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<int> printFromTopToBottom(TreeNode *root){// 特判if (root == nullptr)return {};vector<int> nums;queue<TreeNode *> q;q.push(root);while (!q.empty()){int size = q.size();for (int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();nums.push_back(node->val);if (node->left)q.push(node->left);if (node->right)q.push(node->right);}}return nums;}
};

复杂度分析：

时间复杂度：O(n)，其中 n 是二叉树的节点个数。

空间复杂度：O(n)，其中 n 是二叉树的节点个数。

题目 2：分行从上往下打印二叉树

题目来源：44. 分行从上往下打印二叉树

还是层序遍历，但是每层元素放在一个数组内，最后插入一个新的数组。

代码：

/*** 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>> printFromTopToBottom(TreeNode *root){// 特判if (root == nullptr)return {};vector<vector<int>> levelNums;vector<int> nums;queue<TreeNode *> q;q.push(root);while (!q.empty()){int size = q.size();nums.clear();for (int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();nums.push_back(node->val);if (node->left)q.push(node->left);if (node->right)q.push(node->right);}levelNums.push_back(nums);}return levelNums;}
};

复杂度分析：

时间复杂度：O(n)，其中 n 是二叉树的节点个数。

空间复杂度：O(n)，其中 n 是二叉树的节点个数。

题目 3：之字形打印二叉树

题目来源：45. 之字形打印二叉树

依然是层序遍历，同样是每层元素放在一个数组内，但是设置一个 bool 值 reversed 控制每一层元素数组的次序（若为真，则将该层数组倒序），向答案插入一个新的数组后，reversed 取反，这样就实现了之字形打印。

代码：

/*** 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>> printFromTopToBottom(TreeNode *root){// 特判if (root == nullptr)return {};vector<vector<int>> levelNums;vector<int> nums;bool reversed = false;queue<TreeNode *> q;q.push(root);while (!q.empty()){int size = q.size();nums.clear();for (int i = 0; i < size; i++){TreeNode *node = q.front();q.pop();nums.push_back(node->val);if (node->left)q.push(node->left);if (node->right)q.push(node->right);}if (reversed)reverse(nums.begin(), nums.end());levelNums.push_back(nums);reversed = !reversed;}return levelNums;}
};

复杂度分析：

时间复杂度：O(n)，其中 n 是二叉树的节点个数。

空间复杂度：O(n)，其中 n 是二叉树的节点个数。