괄호와 정수로 구성된 문자열이 있다고 가정합니다. 우리는 그 문자열로부터 이진 트리를 구성해야 합니다. 전체 입력은 이진 트리를 나타냅니다. 0, 한 쌍 또는 두 쌍의 괄호가 뒤에 오는 정수를 보유합니다. 정수는 루트 값을 나타내며 한 쌍의 괄호에는 동일한 구조의 자식 바이너리 트리가 포함됩니다.
따라서 입력이 "4(2(3)(1))(6(5))"와 같으면 출력은 [3,2,1,4,5,6](중위 순회)
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
solve() 함수를 정의하면 s, idx,
가 필요합니다. -
idx>=크기가 s이면 -
-
null 반환
-
-
num :=빈 문자열
-
동안 (idx
-
숫자 :=숫자 + s[idx]
-
(idx를 1씩 증가)
-
-
노드 =값이 num인 새 노드
-
idx
-
(idx를 1씩 증가)
-
노드 왼쪽 :=solve(s, idx)
-
(idx를 1씩 증가)
-
idx
-
(idx를 1씩 증가)
-
노드 오른쪽 :=solve(s, idx)
-
(idx를 1씩 증가)
-
-
-
반환 노드
-
주요 방법에서 다음을 수행하십시오 -
-
아이디:=0
-
temp =값이 -1인 새 노드
-
해결(s, idx) 반환
예시(C++)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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);
} 입력
"4(2(3)(1))(6(5))"
출력
3 2 1 4 5 6