ধরুন আমাদের একটি বাইনারি ট্রি একটি m*n 2D স্ট্রিং অ্যারেতে প্রদর্শন করতে হবে নিম্নলিখিত নিয়মাবলী অনুযায়ী −
- সারি সংখ্যা m দেওয়া বাইনারি ট্রির উচ্চতার সমান হওয়া উচিত।
- কলাম সংখ্যা n সর্বদা একটি বিজোড় সংখ্যা হওয়া উচিত।
- রুট নোডের মান প্রথম সারির সঠিক মাঝপথে রাখা উচিত। কলাম এবং সারি যেখানে রুট নোড অবস্থান করে, বাকি স্পেসটিকে দুটি অংশে ভাগ করবে। এগুলি হল বাম-নিচের অংশ এবং ডান-নিচের অংশ। আমাদের বাম সাবট্রি বাম-নিচের অংশে এবং ডান সাবট্রি ডান-নিচের অংশে প্রিন্ট করা উচিত। এখানে বাম-নিচের অংশ এবং ডান-নিচের অংশ একই আকারের হওয়া উচিত। এমনকি যদি একটি সাবট্রি নন থাকে অন্যটি না থাকে, তবে আমাদের নন সাবট্রির জন্য কিছু প্রিন্ট করার দরকার নেই কিন্তু অন্যটির জন্য তার চেয়ে বড় স্পেস ফাঁকা রাখতে হবে। এখন, যদি দুটি সাবট্রি নন হয়, তবে আমাদের তাদের জন্য স্পেস ফাঁকা রাখার দরকার নেই।
- প্রতিটি অপ্রयुक्त স্পেসে একটি খালি স্ট্রিং থাকা উচিত।
- সাবট্রিগুলি একই নিয়মাবলী অনুসরণ করে প্রদর্শন করুন।
তাই যদি ইনপুট ট্রি হয় −
তবে আউটপুট হবে −
| 1 | ||||||
| 2 | 3 | |||||
| 4 |
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- fill() নামে অন্য একটি মেথড সংজ্ঞায়িত করুন, এটি node, matrix ret, lvl, l এবং r মান নেবে
- যদি node null হয়, তবে ফেরত যান
- ret[lvl, (l + r)/2] := node val স্ট্রিং হিসেবে
- fill(node-এর বাম, ret, lvl+1, l, (l+r)/2)
- fill(node-এর ডান, ret, lvl+1, (l+r+1)/2, r)
- মূল মেথড থেকে নিম্নলিখিত কাজ করুন −
- h := ট্রির উচ্চতা
- leaves = 2^h – 1
- h x leaves ক্রমের একটি ম্যাট্রিক্স তৈরি করুন, এবং এটি খালি স্ট্রিং দিয়ে পূরণ করুন
- fill(root, ret, 0, 0, leaves)
- 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, , , , , ],]
