สมมติว่าเรามีสตริงที่ประกอบด้วยวงเล็บและจำนวนเต็ม เราต้องสร้างต้นไม้ไบนารีจากสตริงนั้น อินพุตทั้งหมดแสดงถึงต้นไม้ไบนารี ซึ่งมีจำนวนเต็มตามด้วยศูนย์ หนึ่ง หรือสองคู่ของวงเล็บ จำนวนเต็มแสดงถึงค่าของราก และคู่ของวงเล็บแต่ละคู่มีต้นไม้ไบนารีลูกที่มีโครงสร้างเหมือนกัน
เช่น ถ้าอินพุตเป็น "4(2(3)(1))(6(5))" ผลลัพธ์จะเป็น [3,2,1,4,5,6] (การท่องไปในออร์เดอร์)
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
กำหนดฟังก์ชัน solve() ซึ่งรับพารามิเตอร์ s และ idx
ถ้า idx >= ขนาดของ s แล้ว ให้คืนค่า null
num := สตริงว่าง
ทำซ้ำ while (idx < ขนาดของ s และ s[idx] ไม่ใช่ '(' และ s[idx] ไม่ใช่ ')') ให้ทำ:
num := num + s[idx]
เพิ่ม idx ขึ้น 1
node = โหนดใหม่ที่มีค่า num
ถ้า idx < ขนาดของ s และ s[idx] เป็น '(' ให้ทำ:
เพิ่ม idx ขึ้น 1
left ของ node := solve(s, idx)
เพิ่ม idx ขึ้น 1
ถ้า idx < ขนาดของ s และ s[idx] เป็น '(' ให้ทำ:
เพิ่ม idx ขึ้น 1
right ของ 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
