การแบนต้นไม้แบนารีเป็น Linked List (Flatten Binary Tree to Linked List) ใน C++

การแบนต้นไม้แบนารีเป็น Linked List (Flatten Binary Tree to Linked List)

แบน (flatten) ต้นไม้แบนารีให้กลายเป็น linked list แบบ in-place โดย right pointer ชี้ไปโหนดถัดไปใน preorder traversal และ left pointer เป็น null

ตัวอย่าง: ต้นไม้ [1,2,5,3,4] → 1→2→3→4→5 (preorder)

ขั้นตอนการแก้ปัญหา (Reverse Post-order Traversal)

1. ตัวแปร global prev = null
2. ฟังก์ชัน flatten(root):
   • ถ้า root == null คืนค่า
   • flatten(root.right) (ขวาก่อน)
   • flatten(root.left) (ซ้ายทีหลัง)
   • root.right = prev, root.left = null
   • prev = root

ทำแบบ reverse post-order (ขวา-ซ้าย-ราก) เพื่อสร้าง linked list จากท้ายมาหน้า

ตัวอย่างโค้ด 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;
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [1,2,5,3,4]

Output: 1, 2, 3, 4, 5 (preorder traversal ของต้นไม้ที่แบนแล้ว)