검지 Offer - 위에서 아래로 두 갈래 트리 인쇄
제목
두 갈래 나무를 위에서 아래로 나누지 않고 인쇄합니다.위에서 아래로 두 갈래 나무의 각 결점을 인쇄하고, 같은 층의 결점은 왼쪽에서 오른쪽의 순서에 따라 인쇄한다.
예제
입력:
8
/ \
6 10
/ \ / \
5 7 9 11
출력:
8 6 10 5 7 9 11문제 풀이 사고방식
이것은 사실 층층이 두루 돌아다니는 것이다.결점을 인쇄할 때마다 결점에 하위 결점이 있으면 결점의 하위 결점을 대기열의 끝에 놓습니다.다음은 대기열의 첫 번째 부분에서 대기열에 가장 먼저 들어간 결점을 꺼내고 대기열의 모든 결점이 인쇄될 때까지 앞의 인쇄를 반복합니다.
코드 구현
#include
#include
#include
struct BiTNode {
int val;
BiTNode* left;
BiTNode* right;
BiTNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
std::vector PrintFromTopToBottom(BiTNode* root) {
//
std::vector result;
//
if (root == nullptr) {
return result;
}
// ：
std::queue qeueTreeNode;
//
qeueTreeNode.push(root);
//
while (!qeueTreeNode.empty()) {
// ：
BiTNode* node = qeueTreeNode.front();
// result
result.push_back(node->val);
//
if (node->left != nullptr) {
qeueTreeNode.push(node->left);
}
if (node->right != nullptr) {
qeueTreeNode.push(node->right);
}
//
qeueTreeNode.pop();
}
return result;
}
};
//
void DestroyBiTree(BiTNode* root)
{
if (root == nullptr) {
return;
}
DestroyBiTree(root->left);
DestroyBiTree(root->right);
// delete
delete root;
root = nullptr;
}
int main(void)
{
Solution sol;
std::vector res;
//
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
for (int i:res) {
std::cout << i;
if (i != res[res.size() - 1]) {
std::cout << ' ';
}
}
// vector，
// 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;
} 제목
지점은 위에서 아래로 두 갈래 나무를 인쇄한다.위에서 아래로 층별로 두 갈래 트리를 인쇄하고, 같은 층의 결점은 왼쪽에서 오른쪽으로 순서대로 인쇄하며, 층마다 한 줄로 인쇄한다.
예제
입력:
8
/ \
6 10
/ \ / \
5 7 9 11
출력:
8
6 10
5 7 9 11문제 풀이 사고방식
두 갈래 나무의 한 줄을 한 줄에 단독으로 인쇄하기 위해서 우리는 두 가지 변수가 필요하다. 한 변수는 현재 층에 아직 인쇄되지 않은 결점을 나타낸다.또 다른 변수는 다음 결점의 수를 나타낸다.
코드 구현
#include
#include
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 qeueTreeNode;
qeueTreeNode.push(root);
//
int nextLevel = 0;
//
int toBePrinted = 1;
while (!qeueTreeNode.empty()) {
BiTNode* node = qeueTreeNode.front();
//
std::cout << node->val;
//
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;
// ，
if (toBePrinted == 0) {
std::cout << std::endl;
toBePrinted = nextLevel;
nextLevel = 0;
}
}
return 0;
}
};
//
void DestroyBiTree(BiTNode* root)
{
if (root == nullptr) {
return;
}
DestroyBiTree(root->left);
DestroyBiTree(root->right);
// delete
delete root;
root = nullptr;
}
int main(void)
{
Solution sol;
//
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;
} 제목
지그재그로 두 갈래 나무를 인쇄하다.함수는 지그재그 순서에 따라 두 갈래 트리를 인쇄합니다. 즉, 첫 번째 줄은 왼쪽에서 오른쪽으로, 두 번째 줄은 오른쪽에서 왼쪽으로, 세 번째 줄은 왼쪽에서 오른쪽으로 인쇄합니다. 다른 줄은 이와 같습니다.
예제
입력:
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문제 풀이 사고방식
지그재그 순서로 두 갈래 나무를 인쇄하려면 두 개의 창고가 필요하다.한 층의 결점을 인쇄할 때 다음 층의 하위 결점을 해당하는 창고에 저장합니다.현재 인쇄된 것이 홀수층(1, 3층 등)이라면 왼쪽 결점을 저장하고 오른쪽 결점을 첫 번째 창고에 저장한다.짝수 레이어 (2, 4 레이어 등) 를 인쇄하는 경우 오른쪽 끝점을 저장한 다음 왼쪽 끝점을 두 번째 창고에 저장합니다.
코드 구현
#include
#include
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 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;
}
};
//
void DestroyBiTree(BiTNode* root)
{
if (root == nullptr) {
return;
}
DestroyBiTree(root->left);
DestroyBiTree(root->right);
// delete
delete root;
root = nullptr;
}
int main(void)
{
Solution sol;
//
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;
} 개인 홈페이지:
www.codeapes.cn
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
