Xây dựng cây nhị phân từ chuỗi trong C++

Giới thiệu

Cho một chuỗi bao gồm các dấu ngoặc đơn và số nguyên. Nhiệm vụ là xây dựng một cây nhị phân từ chuỗi đó. Toàn bộ chuỗi đầu vào đại diện cho một cây nhị phân. Nó chứa một số nguyên theo sau là không, một hoặc hai cặp dấu ngoặc đơn. Số nguyên đại diện cho giá trị của nút gốc, và một cặp dấu ngoặc đơn chứa một cây con nhị phân với cùng cấu trúc.

Ví dụ, nếu đầu vào là "4(2(3)(1))(6(5))", thì đầu ra sẽ là [3,2,1,4,5,6] (duyệt inorder).

Ý tưởng giải thuật

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

1. Định nghĩa hàm solve() nhận tham số chuỗi s và chỉ số idx (truyền tham chiếu).
2. Nếu idx >= s.size(), trả về NULL.
3. Trích xuất số nguyên: đọc các ký tự liên tiếp cho đến khi gặp '(' hoặc ')' để tạo chuỗi num, chuyển thành số nguyên.
4. Tạo nút mới với giá trị num.
5. Nếu ký tự hiện tại là '(', tăng idx và đệ quy xây dựng cây con trái.
6. Sau khi xử lý cây con trái, nếu ký tự tiếp theo vẫn là '(', tăng idx và đệ quy xây dựng cây con phải.
7. Trả về nút gốc vừa tạo.
8. Từ hàm main, khởi tạo idx = 0 và gọi solve(s, idx).

Ví dụ triển khai (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 inorder(TreeNode *root) {
    if (root != NULL) {
        inorder(root->left);
        cout << root->val << " ";
        inorder(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;
        return solve(s, idx);
    }
};

int main() {
    Solution ob;
    TreeNode *root = ob.str2tree("4(2(3)(1))(6(5))");
    inorder(root);
    return 0;
}

Đầu vào

"4(2(3)(1))(6(5))"

Đầu ra

3 2 1 4 5 6