数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中从字符串构建二叉树
假设我们有一个由括号和整数组成的字符串。我们必须从该字符串构建一个二叉树。整个输入表示一个二叉树。它包含一个整数，后面跟着零个、一个或两个括号对。整数表示根节点的值，而括号对包含具有相同结构的子二叉树。
因此，如果输入类似于“4(2(3)(1))(6(5))”，则输出将为 [3,2,1,4,5,6]（中序遍历）
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 solve()，它将接收 s、idx，
如果 idx >= s 的大小，则：
返回 null
num := 空字符串
当 (idx < s 的大小且 s[idx] 不等于 '(' 且 s[idx] 不等于 ')') 时，执行：
num := num + s[idx]
(将 idx 增加 1)
node = 新节点，值为 num
如果 idx < s 的大小且 s[idx] 等于 '('，则：
(将 idx 增加 1)
node 的左子节点 := solve(s, idx)
(将 idx 增加 1)
如果 idx < s 的大小且 s[idx] 等于 '('，则：
(将 idx 增加 1)
node 的右子节点 := solve(s, idx)
(将 idx 增加 1)
返回 node
从主方法执行以下操作：
idx := 0
temp = 新节点，值为 -1
返回 solve(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
更新于: 2020年11月16日
1K+ 次查看
广告