ต้นไม้แบนารีสูงสุด (Maximum Binary Tree) ใน C++

ต้นไม้แบนารีสูงสุด (Maximum Binary Tree)

ให้อาร์เรย์จำนวนเต็มที่ไม่ซ้ำกัน ต้นไม้สูงสุด (Maximum Tree) สร้างขึ้นได้ดังนี้:

• รากเป็นค่าสูงสุดในอาร์เรย์
• ต้นไม้ย่อยซ้ายสร้างจากส่วนซ้ายของค่าสูงสุด
• ต้นไม้ย่อยขวาสร้างจากส่วนขวาของค่าสูงสุด

ขั้นตอนการแก้ปัญหา (Recursive)

1. กำหนดฟังก์ชัน solve(nums, left, right):
2. ถ้า left > right คืนค่า null
3. หา maxIndex และ maxVal ในช่วง [left, right]
4. สร้างโหนดใหม่ด้วย maxVal
5. node.left = solve(nums, left, maxIndex-1)
6. node.right = solve(nums, maxIndex+1, right)
7. คืนค่า node
8. เรียกจาก main: solve(nums, 0, n-1)

ตัวอย่างโค้ด 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* solve(vector<int>& nums, int left, int right) {
        if (left > right) return NULL;
        int maxIdx = left;
        for (int i = left + 1; i <= right; i++)
            if (nums[i] > nums[maxIdx]) maxIdx = i;
        TreeNode* node = new TreeNode(nums[maxIdx]);
        node->left = solve(nums, left, maxIdx - 1);
        node->right = solve(nums, maxIdx + 1, right);
        return node;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return solve(nums, 0, nums.size() - 1);
    }
};

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

Input: [3,2,1,6,0,5]

Output (Inorder): 3 2 1 6 0 5 (โครงสร้างต้นไม้ตามรูป)