Chuyển đổi cây tìm kiếm nhị phân thành danh sách liên kết đơn trong C++

Giới thiệu

Cho cây nhị phân, chuyển đổi thành danh sách liên kết đơn (in-place) theo thứ tự duyệt preorder (Root → Left → Right). Con trỏ right làm next, left đặt NULL.

Ví dụ

Cây: 1 (left: 2, right: 5), 2 (left: 3, right: 4) → Danh sách: 1→2→3→4→5

Ý tưởng giải thuật (Đệ quy ngược - Postorder biến đổi)

Duyệt theo thứ tự: Right → Left → Root. Giữ biến toàn cục prev trỏ đến nút đã xử lý trước đó (trong danh sách kết quả).

1. Đệ quy xử lý right, sau đó left.
2. Gán root->right = prev, root->left = NULL.
3. Cập nhật prev = root.

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;
    }
};

class Solution {
public:
    TreeNode* prev = nullptr;
    
    void flatten(TreeNode* root) {
        if (!root) return;
        flatten(root->right);
        flatten(root->left);
        root->right = prev;
        root->left = nullptr;
        prev = root;
    }
};

// Hàm hỗ trợ tạo cây từ mảng level-order
TreeNode* buildTree(vector<int> v) {
    if (v.empty()) return nullptr;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* cur = q.front(); q.pop();
        if (i < v.size() && v[i] != -1) {
            cur->left = new TreeNode(v[i]);
            q.push(cur->left);
        }
        i++;
        if (i < v.size() && v[i] != -1) {
            cur->right = new TreeNode(v[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

int main() {
    vector<int> v = {1,2,5,3,4,-1,-1,-1,-1,-1,-1};
    TreeNode* root = buildTree(v);
    Solution ob;
    ob.flatten(root);
    
    TreeNode* ptr = root;
    while (ptr) {
        cout << ptr->val << " ";
        ptr = ptr->right;
    }
    return 0;
}

Đầu vào

{1,2,5,3,4}

Đầu ra

1 2 3 4 5