Làm phẳng cây nhị phân thành danh sách liên kết trong C++

Cho cây nhị phân, làm phẳng thành danh sách liên kết tại chỗ (in-place). Duyệt theo thứ tự pre-order: gốc, trái, phải. Ví dụ cây cho kết quả danh sách liên kết 1→2→3→4→5.

Giải thuật

• prev := null.
• Hàm đệ quy solve(root):
  • Nếu root == null trả về.
  • solve(root->right)
  • solve(root->left)
  • root->right = prev, root->left = NULL.
  • prev = root.

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

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

Đầu vào

[1,2,5,3,4]

Đầu ra

1, 2, 3, 4, 5,