文章目录
-
- 1. 题目来源
- 2. 题目说明
- 3. 题目解析
-
- 问题一：I. 从上到下打印二叉树
-
- 方法一：辅助队列+层序遍历+常规解法
- 问题二：II. 从上到下打印二叉树 II
-
- 方法一：辅助队列+层序遍历+常规解法
- 问题三：III. 从上到下打印二叉树 III
-
- 方法一：辅助队列+层序遍历+标志奇偶层+常规解法
- 方法二：辅助双栈+层序遍历+常规解法
1. 题目来源
链接：I. 从上到下打印二叉树
来源：LeetCode——《剑指-Offer》专项
链接：II. 从上到下打印二叉树 II
来源：LeetCode——《剑指-Offer》专项
链接：III. 从上到下打印二叉树 III
来源：LeetCode——《剑指-Offer》专项
2. 题目说明
提示：
-
节点总数 <= 1000
3. 题目解析
问题一：I. 从上到下打印二叉树
方法一：辅助队列+层序遍历+常规解法
很明显的二叉树的层序遍历，采用辅助队列。首先头结点入队，开始
while
循环，再清空队列元素，队首元素出队时将其左右孩子入队，并将该元素
push_back
至
vector
中。当队列为空时循环终止，即二叉树所有节点遍历完毕。
参见代码如下：
// 执行用时 :4 ms, 在所有 C++ 提交中击败了87.08%的用户
// 内存消耗 :14.5 MB, 在所有 C++ 提交中击败了100.00%的用户
/**
* 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> levelOrder(TreeNode* root) {
vector<int> vt;
if (root == nullptr) return vt;
queue<TreeNode*> q;
TreeNode* cur;
q.push(root);
while (!q.empty()) {
for (int i = 0; i < q.size(); ++i) {
cur = q.front();
vt.push_back(cur->val);
q.pop();
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
return vt;
}
};
问题二：II. 从上到下打印二叉树 II
方法一：辅助队列+层序遍历+常规解法
这个问题和问题一本质都是二叉树的层序遍历，只是对结果的输出形式有所变化，这个问题需要返回
vector<vector<int>>
，即将每一层的二叉树数据放进一个
vector<int>
中，再将其作为二维
vector
的元素添加进去就行了。在代码上稍改动即可。改动位置已在代码里标出。
参见代码如下：
// 执行用时 :4 ms, 在所有 C++ 提交中击败了90.01%的用户
// 内存消耗 :15.1 MB, 在所有 C++ 提交中击败了100.00%的用户
/**
* 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>> res;
if (!root) return res;
vector<int> vt;
queue<TreeNode*> q;
TreeNode* cur;
int len = 1;
q.push(root);
while (!q.empty()) {
for (int i = 0; i < len; ++i) {
cur = q.front();
vt.push_back(cur -> val);
q.pop();
if (cur->left) q.push(cur -> left);
if (cur->right) q.push(cur->right);
}
res.push_back(vt); // 改动点
vt.clear(); // 改动点
len = q.size();
}
return res;
}
};
问题三：III. 从上到下打印二叉树 III
方法一：辅助队列+层序遍历+标志奇偶层+常规解法
层序遍历的变种，能够很明显的发现：设二叉树根节点为第 1 层的话，凡是偶数层的层序序列均与原来的序列相反。在此仅需做一个标志即可，对偶数层的
vector
层序序列做
reverse()
即可。
参见代码如下：
// 执行用时 :4 ms, 在所有 C++ 提交中击败了86.05%的用户
// 内存消耗 :15.1 MB, 在所有 C++ 提交中击败了100.00%的用户
/**
* 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>> res;
if (!root) return res;
vector<int> vt;
queue<TreeNode*> q;
TreeNode* cur;
int len = 1, cnt = 1;
q.push(root);
while (!q.empty()) {
for (int i = 0; i < len; ++i) {
cur = q.front();
vt.push_back(cur -> val);
q.pop();
if (cur->left) q.push(cur -> left);
if (cur->right) q.push(cur->right);
}
if (cnt % 2 == 0) reverse(vt.begin(), vt.end()); // 注意点
res.push_back(vt);
vt.clear();
len = q.size();
++cnt;
}
return res;
}
};
方法二：辅助双栈+层序遍历+常规解法
本题方法一当遇到海量数据的时候，
reverse()
的操作较慢，并且也没啥技术含量。在此给出《剑指-Offer》中的
辅助双栈
的解法：
- 首先建立两个辅助栈，
s1、s2
- 现将二叉树根节点入栈
s1
-
s1
s2
s1
-
s2
s1
s2
- 就这样来回倒，直至栈
s1
s2
所以逆序还是要想到
栈
的巧妙使用啊。
参见代码如下：
// 执行用时 :16 ms, 在所有 C++ 提交中击败了6.88%的用户
// 内存消耗 :15.1 MB, 在所有 C++ 提交中击败了100.00%的用户
/**
* 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>> res;
vector<int> vt;
if (root == nullptr) return res;
int len = 1;
stack<TreeNode*> s1, s2;
s2.push(root);
while (!s1.empty() or !s2.empty()) {
while (!s2.empty()) {
TreeNode* tmp = s2.top();
vt.push_back(tmp->val);
s2.pop();
if (tmp->left) s1.push(tmp->left);
if (tmp->right) s1.push(tmp->right);
}
if (vt.size()) res.push_back(vt);
vt.clear();
while (!s1.empty()) {
TreeNode* tmp = s1.top();
vt.push_back(tmp->val);
s1.pop();
if (tmp->right) s2.push(tmp->right);
if (tmp->left) s2.push(tmp->left);
}
if (vt.size()) res.push_back(vt);
vt.clear();
}
return res;
}
};