Cây nhị phân lớn nhất (Maximum Binary Tree) trong C++

Cho mảng số nguyên các phần tử duy nhất. Cây lớn nhất (maximum tree) được xây dựng như sau: gốc là phần tử lớn nhất; cây con trái là cây lớn nhất từ phần tử bên trái của phần tử lớn nhất; cây con phải tương tự bên phải. Xây dựng cây nhị phân lớn nhất. Ví dụ: [3,2,1,6,0,5] cho cây như hình.

Giải thuật

• Định nghĩa solve(nums, left, right):
  • Nếu left > right trả về null.
  • Tìm maxIndex và maxVal trong nums[left..right].
  • Tạo nút node với giá trị maxVal.
  • node->left = solve(nums, left, maxIndex-1)
  • node->right = solve(nums, maxIndex+1, right)
  • Trả về node.
• Gọi solve(nums, 0, nums.size()-1).

Ví dụ mã 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 maxIndex = left, maxVal = nums[left];
        for (int i = left+1; i <= right; i++)
            if (maxVal < nums[i]) { maxVal = nums[i]; maxIndex = i; }
        TreeNode* node = new TreeNode(maxVal);
        node->left = solve(nums, left, maxIndex-1);
        node->right = solve(nums, maxIndex+1, right);
        return node;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return solve(nums, 0, nums.size()-1);
    }
};

Đầu vào

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

Đầu ra

4 3 2 7 1 6