Xây dựng danh sách liên kết 2D từ ma trận bằng C++ (Đệ quy)

Cho một ma trận 2D, chúng ta cần chuyển đổi nó thành một danh sách liên kết hai chiều, trong đó mỗi nút có hai con trỏ: right (sang phải) và down (xuống dưới). Cách tiếp cận đệ quy rất tự nhiên cho bài toán này.

Ví dụ

Ma trận đầu vào:

Danh sách liên kết 2D kết quả:

Thuật toán đệ quy

• Hàm make_2d_list(mat, i, j, m, n) tạo nút tại vị trí (i, j).
• Nếu (i, j) vượt khỏi biên ma trận, trả về NULL.
• Tạo nút mới với giá trị mat[i][j].
• Gán right bằng lời gọi đệ quy cho cột tiếp theo (i, j+1).
• Gán down bằng lời gọi đệ quy cho hàng tiếp theo (i+1, j).
• Trả về nút vừa tạo.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int data;
    TreeNode *right, *down;
    TreeNode(int d) {
        data = d;
        right = down = NULL;
    }
};

void show_2d_list(TreeNode* head) {
    TreeNode *right_ptr, *down_ptr = head;
    while (down_ptr) {
        right_ptr = down_ptr;
        while (right_ptr) {
            cout << right_ptr->data << " ";
            right_ptr = right_ptr->right;
        }
        cout << endl;
        down_ptr = down_ptr->down;
    }
}

TreeNode* make_2d_list(int mat[][3], int i, int j, int m, int n) {
    if (i > n - 1 || j > m - 1) return NULL;
    TreeNode* temp = new TreeNode(mat[i][j]);
    temp->right = make_2d_list(mat, i, j + 1, m, n);
    temp->down = make_2d_list(mat, i + 1, j, m, n);
    return temp;
}

int main() {
    int m = 3, n = 3;
    int mat[][3] = {
        {10, 20, 30},
        {40, 50, 60},
        {70, 80, 90}
    };
    TreeNode* head = make_2d_list(mat, 0, 0, m, n);
    show_2d_list(head);
    return 0;
}

Kết quả

10 20 30
40 50 60
70 80 90

Lưu ý: Cách này đơn giản nhưng có thể gây tràn stack nếu ma trận quá lớn do độ sâu đệ quy.