資料結構
網路
關係資料庫管理系統
作業系統
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+ 次檢視
廣告