สร้างไบนารีทรีจากสตริงใน 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)

• โหนด =โหนดใหม่ที่มีค่า num

• ถ้า idx <ขนาดของ s และ s[idx] เท่ากับ '(' ดังนั้น −

  • (เพิ่ม idx ขึ้น 1)

  • ด้านซ้ายของโหนด :=แก้ (s, idx)

  • (เพิ่ม idx ขึ้น 1)

  • ถ้า idx <ขนาดของ s และ s[idx] เท่ากับ '(' ดังนั้น −

    • (เพิ่ม idx ขึ้น 1)

    • ทางขวาของโหนด :=แก้ (s, idx)

    • (เพิ่ม idx ขึ้น 1)

• โหนดกลับ

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• idx :=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