力扣654题 解题思路和步骤 C++代码实现,c语言试题库及答案详解

问题定义与核心思路

力扣654题要求根据给定不含重复元素的整数数组构建最大二叉树。这种特殊二叉树的特点是根节点为当前数组中的最大值，左子树由最大值左侧子数组构成，右子树由右侧子数组构成。这种结构特征天然适配分治算法（Divide and Conquer），即将原问题分解为多个子问题递归求解。

解题的核心在于理解递归三要素：终止条件、当前层处理、递归调用。当处理空数组时返回空指针，这是递归边界条件。对于非空数组，需要先找到最大值位置，分割左右子数组进行递归构造。这种处理方式的时间复杂度为O(n²)，在数组完全有序时达到最坏情况。

递归函数设计与实现细节

构造递归函数时需要明确参数传递方式。推荐使用数组索引传递而非复制子数组，这在C++中可通过传递起始和结束索引实现。定义辅助函数：TreeNode build(vector& nums, int left, int right)。

具体实现时要注意三点：

1.索引有效性检查（left > right时返回nullptr）；

2.最大值定位需遍历当前区间；

3.左右子树递归范围应为[left, maxIndex-1]和[maxIndex+1, right]。这样处理既能避免数组拷贝，又能准确保留原始元素顺序。

典型测试案例与执行流程

以输入数组[3,2,1,6,0,5]为例：

首次递归找到最大值6，分割为左子数组[3,2,1]和右子数组[0,5]。左子树递归找到3作为根节点，继续分割出空左子数组和[2,1]右子数组。右子树递归找到5作为根节点，分割出[0]左子数组和空右子数组。最终构建的二叉树深度为3，完美符合题目要求。

该案例验证了算法的正确性，展示出分治策略在处理树形结构时的天然优势。测试覆盖了最大值在中间、左子树继续分治、右子树多级递归等关键场景。

C++完整代码实现

class Solution {
public:
    TreeNode constructMaximumBinaryTree(vector& nums) {
        return build(nums,0, nums.size()-1);
    }
    
    TreeNode build(vector& nums, int l, int r) {
        if(l > r) return nullptr;
        int maxIndex = l;
        for(int i=l+1; i<=r; ++i)
            if(nums[i] > nums[maxIndex]) maxIndex = i;
        TreeNode root = new TreeNode(nums[maxIndex]);
        root->left = build(nums, l, maxIndex-1);
        root->right = build(nums, maxIndex+1, r);
        return root;
    }
};

本文系统性地解析了力扣654题的解题思路，通过分治策略实现递归构建最大二叉树。从问题分析、算法设计到代码实现，完整呈现了二叉树类题目的解题范式。掌握这种递归分解问题的思维方式，能够有效提升树形结构相关算法的解题能力。建议读者结合力扣平台测试用例验证代码，并尝试实现时间复杂度更优的单调栈解法以深化理解。