Maximum Binary Tree II ใน C++

โจทย์: กำหนด root ของ maximum tree (ต้นไม้ที่โหนดแต่ละตัวมีค่ามากกว่าทุกโหนดใน subtree) ต้นไม้นี้สร้างจาก list A ด้วยฟังก์ชัน construct():

1. ถ้า A ว่าง: return null
2. หา A[i] ที่มากที่สุด สร้าง root = A[i]
3. Left child = construct(A[0..i-1])
4. Right child = construct(A[i+1..n-1])
5. Return root

เราไม่ได้รับ A โดยตรง แค่ได้ root = construct(A) สมมติ B = A + [val] (เพิ่ม val ท้าย list) รับประกันค่า unique ต้องสร้าง construct(B)

ตัวอย่าง

Input tree: [4,1,3,null,null,2], val = 5

Output tree:

แนวทางแก้ปัญหา (Recursive)

1. สร้างฟังก์ชัน recursive solve(root, val):
   • ถ้า root null: สร้างโหนดใหม่ค่า val คืน
   • ถ้า root->val < val: สร้างโหนดใหม่ค่า val, left = root, คืนโหนดใหม่ (val ใหญ่กว่า root เดิม จะกลายเป็น root ใหม่)
   • มิฉะนั้น: root->right = solve(root->right, val), คืน root

เหตุผล: การเพิ่มค่าต่อท้าย list A จะส่งผลเฉพาะ rightmost path ของ max tree

ตัวอย่างโค้ดเต็ม

#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 tree_level_trav(TreeNode* root) {
    if(!root) return;
    cout << "[";
    queue<TreeNode*> q;
    q.push(root); q.push(NULL);
    while(q.size() > 1) {
        TreeNode *curr = q.front(); q.pop();
        if(curr == NULL) { q.push(NULL); }
        else {
            if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
            if(curr == NULL || curr->val == 0) cout << "null, ";
            else cout << curr->val << ", ";
        }
    }
    cout << "]" << endl;
}

class Solution {
public:
    TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
        if(!root) return new TreeNode(val);
        if(root->val < val) {
            TreeNode* temp = new TreeNode(val);
            temp->left = root;
            return temp;
        }
        root->right = insertIntoMaxTree(root->right, val);
        return root;
    }
};

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

Input

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

Output

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