数据结构
网络
关系型数据库管理系统
操作系统
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+ 次查看
广告