資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中列印二叉樹
假設我們要在一個 m*n 的二維字串陣列中顯示一個二叉樹，遵循以下規則：
- 行數 m 應該與給定二叉樹的高度相同。
- 列數 n 應該始終為奇數。
- 根節點的值應該放在第一行的正中間。根節點所在的列和行將剩餘空間分成兩個部分：左下部分和右下部分。我們應該在左下部分列印左子樹，在右下部分列印右子樹。這裡左下部分和右下部分應該大小相同。即使一個子樹為空而另一個不為空，我們也不需要為那個空的子樹列印任何內容，但仍然需要保留與另一個子樹一樣大的空間。現在，如果兩個子樹都為空，那麼我們不需要為它們都保留空間。
- 每個未使用的空間都應該包含一個空字串。
- 按照相同的規則顯示子樹。
所以如果輸入樹是這樣的：
那麼輸出將是：
| 1 | ||||||
| 2 | 3 | |||||
| 4 |
為了解決這個問題，我們將遵循以下步驟：
- 定義另一個名為 fill() 的方法，它將接收節點、矩陣 ret、層級 lvl 以及 l 和 r 值。
- 如果節點為空，則返回。
- ret[lvl, (l + r)/2] := 節點值作為字串。
- fill(節點的左子節點, ret, lvl+1, l, (l+r)/2)
- fill(節點的右子節點, ret, lvl+1, (l+r+1)/2, r)
- 在主方法中執行以下操作：
- h := 樹的高度。
- 葉子數 = 2^h – 1。
- 建立一個 h x 葉子數 的矩陣，並用空字串填充它。
- fill(根節點, ret, 0, 0, 葉子數)
- 返回 ret。
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
} else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
int getHeight(TreeNode* node){
if(!node)return 0;
return 1 + max(getHeight(node->left), getHeight(node->right));
}
void fill(TreeNode* node, vector<vector<string>>& ret, int lvl, int l, int r){
if(!node || node->val == 0)return;
ret[lvl][(l + r) / 2] = to_string(node->val);
fill(node->left, ret, lvl + 1, l, (l + r) / 2);
fill(node->right, ret, lvl + 1, (l + r + 1) / 2, r);
}
vector<vector<string>> printTree(TreeNode* root) {
int h = getHeight(root);
int leaves = (1 << h) - 1;
vector < vector <string> > ret(h, vector <string>(leaves, ""));
fill(root, ret, 0, 0, leaves);
return ret;
}
};
main(){
vector<int> v = {1,2,3,NULL,4};
Solution ob;
TreeNode *root = make_tree(v);
print_vector(ob.printTree(root));
}輸入
[1,2,3,null,4]
輸出
[[, , , 1, , , , ], [, 2, , , , 3, , ], [, , 4, , , , , ],]
更新於: 2020-05-04
5K+ 次檢視
廣告