Bài toán

Cho hai mảng số nguyên trungTu và hauTu tương ứng biểu diễn dãy trung thứ tự và hậu thứ tự của cùng một cây nhị phân. Nhiệm vụ là xây dựng lại cây nhị phân từ hai dãy này.

Ví dụ 1:

<strong>Đầu vào:</strong> trungTu = [9,3,15,20,7], hauTu = [9,15,7,20,3]<br><strong>Đầu ra:</strong> [3,9,20,null,null,15,7]

Ví dụ 2:

<strong>Đầu vào:</strong> trungTu = [-1], hauTu = [-1]<br><strong>Đầu ra:</strong> [-1]

Phương pháp giải

Bước 1: Gốc cây luôn là phần tử cuối cùng trong dãy hậu thứ tự.
Bước 2: Sử dụng bảng tra cứu nhanh để xác định vị trí của gốc trong dãy trung thứ tự, từ đó phân chia dãy thành nhánh trái và phải.
Bước 3: Áp dụng đệ quy để xây dựng các cây con trái/phải dựa trên kích thước được xác định.

Mã nguồn C++

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

struct Node {
    int giaTri;
    Node* conTrai;
    Node* conPhai;
    Node(int x) : giaTri(x), conTrai(nullptr), conPhai(nullptr) {}
};

class GiaiPhap {
public:
    Node* taoCay(vector<int>& trungTu, vector<int>& hauTu) {
        if (trungTu.empty()) return nullptr;
        
        unordered_map<int, int> bangTra;
        for (int i = 0; i < trungTu.size(); ++i)
            bangTra[trungTu[i]] = i;
            
        return xayDung(trungTu, 0, trungTu.size()-1, 
                       hauTu, 0, hauTu.size()-1, bangTra);
    }
    
private:
    Node* xayDung(vector<int>& trungTu, int trungBatDau, int trungKetThuc,
                 vector<int>& hauTu, int hauBatDau, int hauKetThuc,
                 unordered_map<int, int>& bangTra) {
        if (trungBatDau > trungKetThuc || hauBatDau > hauKetThuc)
            return nullptr;
            
        int giaTriGoc = hauTu[hauKetThuc];
        Node* nutGoc = new Node(giaTriGoc);
        int viTriGoc = bangTra[giaTriGoc];
        
        int doDaiTrai = viTriGoc - trungBatDau;
        int doDaiPhai = trungKetThuc - viTriGoc;
        
        nutGoc->conTrai = xayDung(trungTu, trungBatDau, viTriGoc-1,
                                 hauTu, hauBatDau, hauBatDau+doDaiTrai-1, bangTra);
                                 
        nutGoc->conPhai = xayDung(trungTu, viTriGoc+1, trungKetThuc,
                                hauTu, hauBatDau+doDaiTrai, hauKetThuc-1, bangTra);
                                
        return nutGoc;
    }
};