leetcode题解——654. 最大二叉树

leetcode题解——654. 最大二叉树 2022-07-09 643

题目描述：

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。右子树是通过数组中最大值右边部分构造出的最大二叉树。通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例：

解题思路

看了题目的要求，我闻到了浓浓的分治思想，通过最大值索引区分左右子树区间，分治到底～其实也没那么高大上，实际就是套用先序遍历框架递归建树，分治的思想都交给递归去做了。我们主要针对于当前结点的操作，即找到在[left...right]中nums的最大值，然后new一下建立结点就好啦。

代码

class Solution {
          
   
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
          
   
        if(nums.size() == 0)
            return NULL;

        return helper(nums, 0, nums.size() - 1);
    }

private:
    TreeNode* helper(vector<int>& nums, int left, int right){
          
   
        if(left > right)
            return NULL;
        
        int index = getMaxIndex(nums, left, right);
        TreeNode* root = new TreeNode(nums[index]);

        root->left = helper(nums, left, index - 1);
        root->right = helper(nums, index + 1, right);
        return root;
    }

    int getMaxIndex(vector<int>& nums, int left, int right){
          
   
        int result = -1, index = -1;
        for(int i = left; i <= right; i++){
          
   
            if(nums[i] > result){
          
   
                result = nums[i];
                index = i;
            }
        }
        return index;
    }
};