Giả sử chúng ta phải hiển thị một cây nhị phân trong một mảng chuỗi 2D m * n dựa trên các quy tắc này -
- Số hàng m phải giống với chiều cao của cây nhị phân đã cho.
- Số n của cột phải luôn là số lẻ.
- Giá trị của nút gốc phải được đặt ở chính giữa hàng đầu tiên mà nó có thể được đặt. Cột và hàng nơi nút gốc nằm, sẽ tách không gian còn lại thành hai phần. Đây là phần dưới cùng bên trái và phần dưới cùng bên phải. Chúng ta nên in cây con bên trái ở phần dưới cùng bên trái và in cây con bên phải ở phần dưới cùng bên phải. Ở đây, phần dưới cùng bên trái và phần dưới cùng bên phải có cùng kích thước. Ngay cả khi một cây con không có gì trong khi cây con kia thì không, chúng ta không cần in bất cứ thứ gì cho cây con không có nhưng vẫn cần để lại khoảng trống lớn bằng khoảng trống cho cây con kia. Bây giờ, nếu không có hai cây con nào thì chúng ta không cần để trống cho cả hai cây con.
- Mỗi không gian không sử dụng phải chứa một chuỗi trống.
- Hiển thị các cây con tuân theo các quy tắc tương tự.
Vì vậy, nếu cây đầu vào giống như -
Sau đó, đầu ra sẽ là -
| | | | 1 | | | |
| | 2 | | | | 3 | |
| | | 4 | | | | |
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một phương thức khác được gọi là fill (), Phương thức này sẽ nhận giá trị nút, ma trận ret, lvl, l và r
- nếu nút là null, thì trả về
- ret [lvl, (l + r) / 2]:=nút val dưới dạng chuỗi
- điền vào (bên trái của nút, ret, lvl + 1, l, (l + r) / 2)
- điền vào (bên phải của nút, ret, lvl + 1, (l + r + 1) / 2, r)
- Từ phương pháp chính, hãy làm như sau -
- h:=chiều cao của cây
- lá =2 ^ h - 1
- tạo một ma trận có thứ tự h x để lại và điền vào ma trận này bằng các chuỗi trống
- điền vào (gốc, ret, 0, 0, lá)
- trả lời lại
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
[1,2,3,null,4]
Đầu ra
[[, , , 1, , , , ], [, 2, , , , 3, , ], [, , 4, , , , , ],]