【LeetCode二叉树#11】最大二叉树（构造二叉树）

最大二叉树

力扣题目地址(opens new window)

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

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例：

654.最大二叉树

提示：

给定的数组的大小在 [1, 1000] 之间。

思路

就按照题意来就行，这里给了一种二叉树的构造规则，根据该规则构造的二叉树称为最大二叉树

模拟一下整个流程：

给了一个数组输入[3,2,1,6,0,5]

先找出其中的最大值，即6。该值最为最大二叉树的根节点

然后上述数组被分为了两部分：[3,2,1] 和 [0,5]

左边部分用于构建最大二叉树的左分支

右边部分用于构建最大二叉树的右分支

先来看左边子树（以 6 为根节点），在左数组中找出最大值，即3。该值为最大二叉树的左子树的根节点

于是 [3,2,1] 又被分成了 [] （左边没有数值了）和 [2,1] ，本次分割后左边数组是没有值了，因此以 3 为根节点的左子树也没有了

因为 [2,1] 属于 [3,2,1] 的 "右部分" ，所以要用来构建以 3 为根节点的右子树

以此类推将剩下的数处理完毕

右边子树（以 6 为根节点）的构建过程同理

可见，上述过程是递归的经典应用场景

代码分析

1、确定递归函数的参数和返回值

题干给了，输入是一个整数数组，那递归函数的输入应该也是这个

然后最后的结果是构造一个最大二叉树，那么返回值应该是二叉树的根节点

这里可以直接用模板给的函数就行

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {

    }
};

2、确定终止条件

题干说了，输入数组大小一定大于1，那么不用考虑小于1的情况

当输入数组大小为1时（经过不断的递归分割最后肯定都是1），说明已经到了叶子节点

那么递归构造应该结束，此时需要创建一个新节点来保存当前数组的值，并返回该节点

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
		//定义一个新节点用于保存数组的最后一个值
        TreeNode* node;
        if(num.size() == 1){
            node->val = num[0];
            return node;
        }
    }
};

3、确定单层处理逻辑

一共分为三步：

遍历输入数组，确定当前最大值。最大值本身用于构造根节点，下标则用于分割数组
在最大值下标所在的左区间构造左子树
在最大值下标所在的右区间构造右子树

第一步，遍历输入数组，确定当前最大值。最大值本身用于构造根节点，下标则用于分割数组对不

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
		//定义一个新节点用于保存数组的最后一个值
        TreeNode* node;
        if(num.size() == 1){
            node->val = num[0];
            return node;
        }
        //分别定义用于存放最大值及其下标的变量
        int maxValue = 0;
        int maxValueIndex = 0;
        //遍历最大值
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        //创建根节点
        TreeNode* node = new TreeNode(maxValue);       
    }
};

第二步，最大值所在的下标左区间构造左子树

注意，需要判断左区间是否有值（继续递归的条件是至少得有一个值吧），没有就直接返回node

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
		//定义一个新节点用于保存数组的最后一个值
        if(num.size() == 1){
            TreeNode* node = new TreeNode(nums[0]);
            return node;
        }
        //分别定义用于存放最大值及其下标的变量
        int maxValue = 0;
        int maxValueIndex = 0;
        //遍历最大值
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        //创建根节点
        TreeNode* node = new TreeNode(maxValue); 
        
        //处理左区间，构建左子树
        //先判断左区间是否有值
        if(maxValueIndex > 0){
            //分割得到左区间数组
            vector<int> leftVec(nums.begin(), nums.begin() + maxValueIndex);
            //利用左区间递归构建左子树
            node->left = constructMaximumBinaryTree(leftVec);
        }
        
        //处理右区间，构建右子树
        //先判断右区间是否有值
        if(maxValueIndex < nums.size() - 1){
            //分割得到右区间数组
            vector<int> leftVec(nums.begin() + maxValueIndex + 1, nums.end());
            //利用右区间递归构建右子树
            node->left = constructMaximumBinaryTree(leftVec);
        }
        return node;
    }
};