1. 題目 1
不分行從上到下打印二叉樹(shù)虱颗。從上到下打印出二叉樹(shù)的每個(gè)結(jié)點(diǎn)诚些，同一層的結(jié)點(diǎn)按照從左到右的順序打印汤踏。
1.1 示例
輸入：
8
/ \
6 10
/ \ / \
5 7 9 11
輸出：
8 6 10 5 7 9 11
1.2 解題思路
這個(gè)其實(shí)就是層序遍歷涝涤。每次打印一個(gè)結(jié)點(diǎn)的時(shí)候，若該結(jié)點(diǎn)有子結(jié)點(diǎn)淫僻，則讓該結(jié)點(diǎn)的子結(jié)點(diǎn)放到一個(gè)隊(duì)列的末尾诱篷。接下來(lái)到隊(duì)列的首部取出最早進(jìn)入隊(duì)列的結(jié)點(diǎn)，不斷重復(fù)前面的打印嘁傀，直至隊(duì)列中所有的結(jié)點(diǎn)都被打印出來(lái)兴蒸。
1.3 代碼實(shí)現(xiàn)
#include <iostream>
#include <vector>
#include <queue>
struct BiTNode {
int val;
BiTNode* left;
BiTNode* right;
BiTNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
std::vector<int> PrintFromTopToBottom(BiTNode* root) {
// 存儲(chǔ)打印結(jié)果
std::vector<int> result;
// 邊界條件
if (root == nullptr) {
return result;
}
// 輔助容器：隊(duì)列
std::queue<BiTNode*> qeueTreeNode;
// 根結(jié)點(diǎn)入隊(duì)
qeueTreeNode.push(root);
// 遍歷隊(duì)列
while (!qeueTreeNode.empty()) {
// 輔助指針：指向隊(duì)頭
BiTNode* node = qeueTreeNode.front();
// 打印結(jié)果存儲(chǔ)到result中
result.push_back(node->val);
// 根結(jié)點(diǎn)的子結(jié)點(diǎn)入隊(duì)
if (node->left != nullptr) {
qeueTreeNode.push(node->left);
}
if (node->right != nullptr) {
qeueTreeNode.push(node->right);
}
// 根結(jié)點(diǎn)出隊(duì)
qeueTreeNode.pop();
}
return result;
}
};
// 銷毀二叉樹(shù)
void DestroyBiTree(BiTNode* root)
{
if (root == nullptr) {
return;
}
DestroyBiTree(root->left);
DestroyBiTree(root->right);
// 從最左依次 delete 至根結(jié)點(diǎn)
delete root;
root = nullptr;
}
int main(void)
{
Solution sol;
std::vector<int> res;
// 構(gòu)造一個(gè)二叉樹(shù)
BiTNode* root = new BiTNode(8);
root->left = new BiTNode(6);
root->right = new BiTNode(10);
root->left->left = new BiTNode(5);
root->left->right = new BiTNode(7);
root->right->left = new BiTNode(9);
root->right->right = new BiTNode(11);
res = sol.PrintFromTopToBottom(root);
// 遍歷vector，C++ 11 標(biāo)準(zhǔn)支持
for (int i:res) {
std::cout << i;
if (i != res[res.size() - 1]) {
std::cout << ' ';
}
}
// 遍歷vector细办，打印結(jié)果
// for (unsigned int i = 0; i < res.size(); ++i) {
// std::cout << res[i];
// if (i != res.size() - 1) {
// std::cout << ' ';
// }
// }
std::cout << std::endl;
DestroyBiTree(root);
return 0;
}
2. 題目 2
分行從上到下打印二叉樹(shù)橙凳。從上到下按層打印二叉樹(shù)，同一層的結(jié)點(diǎn)按從左到右的順序打印笑撞，每一層打印到一行岛啸。
2.1 示例
輸入：
8
/ \
6 10
/ \ / \
5 7 9 11
輸出：
8
6 10
5 7 9 11
2.2 解題思路
為了把二叉樹(shù)的每一行單獨(dú)打印到一行里，我們需要兩個(gè)變量：一個(gè)變量表示當(dāng)前層中還未打印的結(jié)點(diǎn)數(shù)茴肥；另一個(gè)變量表示下一層結(jié)點(diǎn)的數(shù)目坚踩。
2.3 代碼實(shí)現(xiàn)
#include <iostream>
#include <queue>
struct BiTNode {
int val;
BiTNode* left;
BiTNode* right;
BiTNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int PrintTreesInLines(BiTNode* root) {
// 邊界條件
if (root == nullptr) {
return -1;
}
std::queue<BiTNode*> qeueTreeNode;
qeueTreeNode.push(root);
// 下一層的結(jié)點(diǎn)數(shù)
int nextLevel = 0;
// 當(dāng)前層中未打印的結(jié)點(diǎn)數(shù)
int toBePrinted = 1;
while (!qeueTreeNode.empty()) {
BiTNode* node = qeueTreeNode.front();
// 打印結(jié)果
std::cout << node->val;
// 打印結(jié)果之間用空格隔開(kāi)
if (toBePrinted != 1) {
std::cout << ' ';
}
if (node->left != nullptr) {
qeueTreeNode.push(node->left);
++nextLevel;
}
if (node->right != nullptr) {
qeueTreeNode.push(node->right);
++nextLevel;
}
qeueTreeNode.pop();
--toBePrinted;
// 當(dāng)前層的所有結(jié)點(diǎn)已打印完畢，可以繼續(xù)打印下一層
if (toBePrinted == 0) {
std::cout << std::endl;
toBePrinted = nextLevel;
nextLevel = 0;
}
}
return 0;
}
};
// 銷毀二叉樹(shù)
void DestroyBiTree(BiTNode* root)
{
if (root == nullptr) {
return;
}
DestroyBiTree(root->left);
DestroyBiTree(root->right);
// 從最左依次 delete 至根結(jié)點(diǎn)
delete root;
root = nullptr;
}
int main(void)
{
Solution sol;
// 構(gòu)造一個(gè)二叉樹(shù)
BiTNode* root = new BiTNode(8);
root->left = new BiTNode(6);
root->right = new BiTNode(10);
root->left->left = new BiTNode(5);
root->left->right = new BiTNode(7);
root->right->left = new BiTNode(9);
root->right->right = new BiTNode(11);
sol.PrintTreesInLines(root);
std::cout << std::endl;
DestroyBiTree(root);
return 0;
}
3. 題目 3
之字形打印二叉樹(shù)瓤狐。請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形順序打印二叉樹(shù)瞬铸，即第一行按照從左到右的順序打印，第二行按照從右到左的順序打印础锐，第三行再按照從左到右的順序打印嗓节，其它行以此類推。
3.1 示例
輸入：
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
輸出：
1
3 2
4 5 6 7
15 14 13 12 11 10 9 8
3.2 解題思路
按之字形順序打印二叉樹(shù)需要兩個(gè)棧皆警。在打印某一層的結(jié)點(diǎn)時(shí)拦宣，把下一層的子結(jié)點(diǎn)保存到相應(yīng)的棧里。若當(dāng)前打印的是奇數(shù)層（第 1 、3 層等）鸵隧，則先保存左子結(jié)點(diǎn)再保存右子結(jié)點(diǎn)到第一個(gè)棧里绸罗；若打印的是偶數(shù)層（第 2 、4層等）豆瘫，則先保存右子結(jié)點(diǎn)再保存左子結(jié)點(diǎn)到第二個(gè)棧里珊蟀。
3.3 代碼實(shí)現(xiàn)
#include <iostream>
#include <stack>
struct BiTNode {
int val;
BiTNode* left;
BiTNode* right;
BiTNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
int PrintTreesInZigzag(BiTNode* root) {
// 邊界條件
if (root == nullptr) {
return -1;
}
std::stack<BiTNode*> stackLevels[2];
int current = 0;
int next = 1;
stackLevels[current].push(root);
while (!stackLevels[0].empty() || !stackLevels[1].empty()) {
BiTNode* node = stackLevels[current].top();
stackLevels[current].pop();
std::cout << node->val;
if (!stackLevels[current].empty()) {
std::cout << ' ';
}
if (current == 0) {
if (node->left != nullptr) {
stackLevels[next].push(node->left);
}
if (node->right != nullptr) {
stackLevels[next].push(node->right);
}
} else {
if (node->right != nullptr) {
stackLevels[next].push(node->right);
}
if (node->left != nullptr) {
stackLevels[next].push(node->left);
}
}
if (stackLevels[current].empty()) {
std::cout << std::endl;
current = 1 - current;
next = 1 - next;
}
}
return 0;
}
};
// 銷毀二叉樹(shù)
void DestroyBiTree(BiTNode* root)
{
if (root == nullptr) {
return;
}
DestroyBiTree(root->left);
DestroyBiTree(root->right);
// 從最左依次 delete 至根結(jié)點(diǎn)
delete root;
root = nullptr;
}
int main(void)
{
Solution sol;
// 構(gòu)造一個(gè)二叉樹(shù)
BiTNode* root = new BiTNode(1);
root->left = new BiTNode(2);
root->right = new BiTNode(3);
root->left->left = new BiTNode(4);
root->left->right = new BiTNode(5);
root->right->left = new BiTNode(6);
root->right->right = new BiTNode(7);
root->left->left->left = new BiTNode(8);
root->left->left->right = new BiTNode(9);
root->left->right->left = new BiTNode(10);
root->left->right->right = new BiTNode(11);
root->right->left->left = new BiTNode(12);
root->right->left->right = new BiTNode(13);
root->right->right->left = new BiTNode(14);
root->right->right->right = new BiTNode(15);
sol.PrintTreesInZigzag(root);
std::cout << std::endl;
DestroyBiTree(root);
return 0;
}
個(gè)人主頁(yè)：
