Khôi phục cây từ duyệt tiền thứ tự trong C++

Cho chuỗi S là kết quả duyệt tiền thứ tự (preorder) cây nhị phân: tại mỗi nút depth D, in D dấu '-' rồi giá trị nút. Gốc depth 0. Nếu nút chỉ có 1 con, chắc chắn là con trái. Khôi phục cây từ S.

Ví dụ: "1-2--3--4-5--6--7" → cây như hình.

Giải pháp

Sử dụng stack để theo dõi đường đi từ gốc:

• Duyệt chuỗi S, phân tích level (số '-') và num (giá trị)
• Stack lưu các nút trên đường đi hiện tại
• Khi đọc xong một nút:
  • Pop stack cho đến khi size == level (đến cha)
  • Tạo nút mới
  • Nếu stack không rỗng và top chưa có con trái → gán con trái
  • Ngược lại nếu stack không rỗng → gán con phải
  • Push nút mới vào stack
• Cuối cùng pop cho đến size=1, trả về top (gốc)

Ví dụ mã 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* recoverFromPreorder(string S) { 
        stack<TreeNode*> st; 
        int i = 0, n = S.size(); 
        int lvl = 0, num = 0; 
        
        while (i < n) { 
            for (lvl = 0; S[i] == '-'; lvl++, i++); 
            num = 0; 
            while (i < n && S[i] != '-') { 
                num = num * 10 + (S[i] - '0'); 
                i++; 
            } 
            while (st.size() > 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; 
}

Đầu vào

"1-2--3--4-5--6--7"

Đầu ra

3 2 4 1 6 5 7