พลิก Binary Tree กลับหัวใน C++

สมมติว่าเรามี binary tree ที่โหนดขวาทั้งหมดเป็น leaf nodes ที่มี sibling หรือว่างเปล่า เราต้องพลิกมันกลับหัว (upside down) ให้โหนดขวาเดิมกลายเป็น left leaf nodes คืนค่า root ใหม่

ตัวอย่าง: อินพุต [1,2,3,4,5] ผลลัพธ์: [4,5,2,#,#,3,1]

วิธีแก้ปัญหา (Recursive)

1. ฟังก์ชัน solve(node, parent, sibling)
   • base case: node ว่าง คืนค่า NULL
   • เก็บ child = node->left, currSib = node->right
   • ปรับ pointer: node->left = sibling, node->right = parent
   • ถ้าไม่มี child และ currSib คืนค่า node (root ใหม่)
   • เรียกซ้ำ solve(child, node, currSib)
2. เรียก solve(root, NULL, NULL)

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

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

void inord(TreeNode *root){ 
    if(root != NULL){ 
        inord(root->left); 
        cout << root->val << " "; 
        inord(root->right); 
    } 
} 

class Solution { 
public: 
    TreeNode* solve(TreeNode* node, TreeNode* par, TreeNode* sibling){ 
        if (!node || node->val == 0) return NULL; 
        TreeNode* child = node->left; 
        TreeNode* currSib = node->right; 
        node->left = sibling; 
        node->right = par; 
        if (!child && !currSib) return node; 
        return solve(child, node, currSib); 
    } 
    TreeNode* upsideDownBinaryTree(TreeNode* root) { 
        return solve(root, NULL, NULL); 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {1,2,3,4,5}; 
    TreeNode *root = make_tree(v); 
    inord(ob.upsideDownBinaryTree(root)); 
}

ข้อมูลนำเข้า

[1,2,3,4,5]

ผลลัพธ์

[4,5,2,null,null,3,1]