이러한 규칙에 따라 m*n 2D 문자열 배열에 이진 트리를 표시해야 한다고 가정해 보겠습니다. -
- 행 번호 m은 주어진 이진 트리의 높이와 같아야 합니다.
- 열 번호 n은 항상 홀수여야 합니다.
- 루트 노드의 값은 넣을 수 있는 첫 번째 행의 정확히 중간에 넣어야 합니다. 루트 노드가 있는 열과 행은 나머지 공간을 두 부분으로 분리합니다. 좌측하단부와 우측하단부 입니다. 왼쪽 하위 트리를 왼쪽 하단 부분에 인쇄하고 오른쪽 하위 트리를 오른쪽 하단 부분에 인쇄해야 합니다. 여기서 왼쪽 아래 부분과 오른쪽 아래 부분은 크기가 같아야 합니다. 한 하위 트리가 none이고 다른 하위 트리가 아니더라도 none 하위 트리에 대해 아무 것도 인쇄할 필요가 없지만 여전히 다른 하위 트리만큼 큰 공간을 남겨둘 필요가 있습니다. 이제 두 개의 하위 트리가 없는 경우 두 하위 트리에 공간을 둘 필요가 없습니다.
- 사용하지 않은 각 공간에는 빈 문자열이 포함되어야 합니다.
- 동일한 규칙에 따라 하위 트리를 표시합니다.
따라서 입력 트리가 다음과 같은 경우 -
그러면 출력은 -
가 됩니다.| | | | 1 | | | |
| | 2 | | | | 3 | |
| | | 4 | | | | |
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- fill()이라는 다른 메서드를 정의합니다. 이것은 노드, 행렬 ret, lvl, l 및 r 값을 사용합니다.
- 노드가 null이면 반환
- ret[lvl, (l + r)/2] :=문자열로 노드 val
- 채우기(노드 왼쪽, ret, lvl+1, l, (l+r)/2)
- fill(노드 오른쪽, ret, lvl+1, (l+r+1)/2, r)
- 주요 방법에서 다음을 수행하십시오 -
- h :=나무의 높이
- 잎 =2^h – 1
- h x 잎의 행렬을 만들고 이를 빈 문자열로 채웁니다.
- 채우기(루트, ret, 0, 0, 잎)
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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, , , , , ],]