二叉树 – 最大二叉树

最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

该题和二叉树 – 从中序和后序序列构造二叉树基本一致，都是使用递归建立二叉树，同时不需要像该题维护四个数组。

经典步骤：

• 1 找到最大值的索引和数值，并创建root节点
• 2 切割得到左子数组和右子数组
• 3 递归左子数组和右子数组

代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* traversal(vector& nums){
        if (nums.size() == 0) return nullptr;
        // 1 找到最大值与下标，并创建root节点
        int rootIndex, rootValue=INT_MIN;
        for(int i = 0; i < nums.size(); i++){
            if (rootValue < nums[i]){
                rootValue = nums[i];
                rootIndex = i;
            }
        }
        TreeNode* root = new TreeNode(rootValue);

        // 2 找到左子数组和右子数组
        vector leftNums(nums.begin(), nums.begin()+rootIndex);
        vector rightNums(nums.begin()+rootIndex+1, nums.end());

        // 3 递归左子树
        root->left = traversal(leftNums);
        // 4 递归右子树
        root->right = traversal(rightNums);

        return root;
    }

    TreeNode* constructMaximumBinaryTree(vector& nums) {
        return traversal(nums);
    }
};