Giả sử chúng ta có một chuỗi bao gồm dấu ngoặc đơn và số nguyên. Chúng ta phải xây dựng một cây nhị phân từ chuỗi đó. Toàn bộ đầu vào đại diện cho một cây nhị phân. Nó chứa một số nguyên theo sau là 0, một hoặc hai cặp dấu ngoặc đơn. Số nguyên đại diện cho giá trị của gốc và một cặp ngoặc chứa cây nhị phân con có cùng cấu trúc.
Vì vậy, nếu đầu vào giống như "4 (2 (3) (1)) (6 (5))", thì đầu ra sẽ là [3,2,1,4,5,6] (inorder traversal)
Để 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 hàm giải quyết (), điều này sẽ nhận s, idx,
-
nếu idx> =kích thước của s, thì -
-
trả về null
-
-
num:=chuỗi rỗng
-
while (idx
-
num:=num + s [idx]
-
(tăng idx lên 1)
-
-
node =new node với giá trị num
-
nếu idx
-
(tăng idx lên 1)
-
bên trái của nút:=giải quyết (s, idx)
-
(tăng idx lên 1)
-
nếu idx
-
(tăng idx lên 1)
-
bên phải của nút:=giải quyết (s, idx)
-
(tăng idx lên 1)
-
-
-
nút trả lại
-
Từ phương thức chính, hãy làm như sau -
-
idx:=0
-
temp =nút mới với giá trị -1
-
trả về giải quyết (s, idx)
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* solve(string s, int& idx){
if (idx >= s.size())
return NULL;
string num = "";
while (idx < s.size() && s[idx] != '(' && s[idx] != ')') {
num += s[idx];
idx++;
}
TreeNode* node = new TreeNode(stoi(num));
if (idx < s.size() && s[idx] == '(') {
idx++;
node->left = solve(s, idx);
idx++;
if (idx < s.size() && s[idx] == '(') {
idx++;
node->right = solve(s, idx);
idx++;
}
}
return node;
}
TreeNode* str2tree(string s) {
int idx = 0;
TreeNode* temp = new TreeNode(-1);
return solve(s, idx);
}
};
main(){
Solution ob;
TreeNode *root = ob.str2tree("4(2(3)(1))(6(5))");
inord(root);
} Đầu vào
"4(2(3)(1))(6(5))"
Đầu ra
3 2 1 4 5 6