คำอธิบายโจทย์
Preorder DFS: แสดง D dash (D=depth) ตามด้วยค่าโหนด ราก depth=0 ลูกเดียวเป็น left child เสมอ กู้คืนต้นไม้จาก string S
ตัวอย่าง
S = "1-2--3--4-5--6--7" → Tree structure
Inorder: 3 2 4 1 6 5 7
วิธีแก้ปัญหา
ใช้ Stack ติดตามโหนดปัจจุบัน:
- อ่าน dashes นับ depth (lvl)
- อ่านตัวเลข (num)
- Pop stack จน size == lvl (ย้อนกลับไป parent)
- สร้างโหนดใหม่ attach เป็น left หรือ right ของ stack top
- Push โหนดใหม่เข้า stack
- สุดท้าย pop จนเหลือ 1 → root
การทำงานของโค้ด
#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) { inord(root->left); cout<val<<" "; inord(root->right); }
}
class Solution {
public:
TreeNode* recoverFromPreorder(string S) {
stack<TreeNode*> st;
int i=0, n=S.size(), lvl=0, num=0;
while(i lvl) st.pop();
TreeNode* temp = new TreeNode(num);
if(!st.empty() && !st.top()->left) st.top()->left = temp;
else if(!st.empty()) st.top()->right = temp;
st.push(temp);
}
while(st.size() > 1) st.pop();
return st.empty() ? NULL : st.top();
}
};
int main() {
Solution ob;
TreeNode* root = ob.recoverFromPreorder("1-2--3--4-5--6--7");
inord(root);
return 0;
}
อินพุต
"1-2--3--4-5--6--7"
เอาต์พุต
3 2 4 1 6 5 7
