力扣第654题 最大二叉树 c++注释版

题目

654. 最大二叉树

中等

相关标签

栈 树 数组 分治 二叉树 单调栈 

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

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

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

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums 中的所有整数 互不相同

思路和解题方法

       首先，创建一个初始化值为0的根节点node。

然后，判断给定数组nums的大小，如果数组只有一个元素，则将该元素作为根节点的值，并返回该节点。

接下来，定义变量maxval和maxvalindex，分别用于记录数组中的最大值和它在数组中的索引。

通过遍历数组，找到最大值和对应的索引。

根据最大值创建一个新的根节点，并赋值给node。

然后，根据最大值的索引，将数组切割成两部分：左半部分是最大值左边的元素，右半部分是最大值右边的元素。

对左半部分递归调用constructMaximumBinaryTree函数构建左子树，并将返回的结果赋值给根节点的左子节点。

对右半部分递归调用constructMaximumBinaryTree函数构建右子树，并将返回的结果赋值给根节点的右子节点。

最后，返回根节点node。

复杂度

        时间复杂度:

                O(n)

时间复杂度：O(n)，其中 n 是数组 nums的长度。单调栈求解左右边界和构造树均需要 O(n)的时间。

        空间复杂度

                O(n)

空间复杂度：O(n)，即为单调栈和数组 tree需要使用的空间。

c++ 代码

class Solution { // 定义一个名为Solution的类
public: // 类内部的公共成员开始
 
    // 定义一个方法 constructMaximumBinaryTree，该方法接受一个整数向量 nums 作为输入
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) { 
        // 创建一个默认的TreeNode对象，值为0，并命名为node
        TreeNode *node = new TreeNode(0); 
        // 如果nums只有一个元素，直接将该元素赋值给node的val，并返回node
        if(nums.size() == 1) {
            node->val = nums[0];
            return node; 
        }
        // 初始化最大值为0，以及最大值所在的索引为0
        int maxval = 0;
        int maxvalindex = 0;
        // 遍历整个nums数组，找到最大的值以及其索引
        for(int i=0;isize();i++) {
            if(nums[i]>maxval) {
                maxval = nums[i];
                maxvalindex = i;
            } 
        }
        // 创建一个新的TreeNode对象，值最大值maxval，并赋值给node
        node = new TreeNode(maxval);
        // 如果最大值的索引大于0，说明最大值不是数组的第一个元素，那么在左子树中应包含到最大值索引位置的元素
        if(maxvalindex>0) {
            vector<int> newvec(nums.begin(),nums.begin() +maxvalindex); // 创建新的向量，包含原数组的从头到最大值索引位置的元素
            node->left = constructMaximumBinaryTree(newvec); // 递归构造左子树，将返回的节点赋值给node的左子节点
        }
        // 如果最大值的索引小于数组长度减1，说明最大值不是数组的最后一个元素，那么在右子树中应包含从最大值索引位置到数组末尾的元素
        if(maxvalindexsize()-1) {
            vector<int> newvec(nums.begin()+maxvalindex+1,nums.end()); // 创建新的向量，包含原数组从最大值索引位置到末尾的元素
            node->right = constructMaximumBinaryTree(newvec); // 递归构造右子树，将返回的节点赋值给node的右子节点
        }
        // 返回构造好的二叉树的根节点node
        return node;
    }
};

c++优化后的代码

class Solution { // 定义一个类名为Solution。
private: // 这个类的私有部分的开始。
    // 在左闭右开区间[left, right)，构造二叉树
    TreeNode* traversal(vector<int>& nums, int left, int right) { // 定义一个私有方法traversal，它接收一个整数向量nums（通过引用传递，以便在函数内部修改原数组）和两个整数left和right作为参数。它返回一个指向TreeNode的指针。
        if (left >= right) return nullptr; // 如果left大于或等于right，则返回空指针，因为这意味着区间内没有元素来构造二叉树。
 
        // 分割点下标：maxValueIndex
        int maxValueIndex = left; // 初始化maxValueIndex为left，因为left是当前子数组的起始索引，还没有被检查过。
        for (int i = left + 1; i < right; ++i) { // 从left+1开始遍历到right-1。
            if (nums[i] > nums[maxValueIndex]) maxValueIndex = i; // 如果当前元素大于maxValueIndex所在位置的元素，则更新maxValueIndex。
        }
 
        TreeNode* root = new TreeNode(nums[maxValueIndex]); // 创建一个新的TreeNode对象，其值是nums中最大值，并把它赋值给root。
 
        // 左闭右开：[left, maxValueIndex)
        root->left = traversal(nums, left, maxValueIndex); // 对左半部分递归调用traversal方法并把返回的树节点赋值给root的左子节点。
 
        // 左闭右开：[maxValueIndex + 1, right)
        root->right = traversal(nums, maxValueIndex + 1, right); // 对右半部分递归调用traversal方法并把返回的树节点赋值给root的右子节点。
 
        return root; // 返回构造好的二叉树的根节点。
    }
public: // 这个类的公共部分的开始。
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) { // 定义一个公共方法constructMaximumBinaryTree，它接收一个整数向量nums（通过引用传递，以便在函数内部修改原数组）并返回一个指向TreeNode的指针。
        return traversal(nums, 0, nums.size()); // 对整个数组调用traversal方法并返回结果。
    }
};

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。