โปรแกรมแปลงต้นไม้ค้นหาไบนารีเป็นรายการเชื่อมเดี่ยวใน C++

สมมติว่าเรามีต้นไม้ไบนารี เราต้องแปลงนี้เป็นรายการเชื่อมเดี่ยว (แบบ in-place)

เช่น ถ้าอินพุตเป็น:

ผลลัพธ์จะเป็น:

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:

• ตั้ง prev := null

• กำหนดฟังก์ชันแบบเรียกซ้ำ solve() ที่รับ root เป็นอินพุต

• ถ้า root เป็น null ให้คืนค่า

• solve(ขวาของ root)

• solve(ซ้ายของ root)

• ขวาของ root := prev, ซ้ายของ root := null

• prev := root

ตัวอย่าง

#include <bits/stdc++.h> using namespace std; class TreeNode{    public:    int val;    TreeNode *left, *right;    TreeNode(int data){       val = data;       left = NULL;       right = NULL;    } }; void insert(TreeNode **root, int val){    queue<TreeNode*> q;    q.push(*root);    while(q.size()){       TreeNode *temp = q.front();       q.pop();       if(!temp->left){          if(val != NULL)             temp->left = new TreeNode(val);          else             temp->left = new TreeNode(0);             return;       }else{          q.push(temp->left);       }       if(!temp->right){          if(val != NULL)             temp->right = new TreeNode(val);          else             temp->right = new TreeNode(0);          return;       }else{          q.push(temp->right);       }    } } TreeNode *make_tree(vector<int> v){    TreeNode *root = new TreeNode(v[0]);    for(int i = 1; i<v.size(); i++){       insert(&root, v[i]);    }    return root; } 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;    } }; main(){    vector<int> v = {1,2,5,3,4};    TreeNode *root = make_tree(v);    Solution ob;    (ob.flatten(root));    TreeNode *ptr = root;    while(ptr != NULL && ptr->val != 0){       cout << ptr->val << ", ";       ptr = ptr->right;    } }

อินพุต

{1,2,5,3,4}

เอาต์พุต

1, 2, 3, 4, 5,