力扣654题 解题思路和步骤 C++代码实现

一、题目背景与核心概念

力扣654题要求根据给定的数组构建一棵最大二叉树。最大二叉树的定义是：每个节点的值都是其子树中的最大值。我们需要理解二叉树的概念及其在实际问题中的应用，要熟悉递归算法的基本思想。在开始编码之前，我们需要明确如何找到数组中的最大值并将其作为根节点，递归地处理左右子数组。

二、构建最大二叉树的步骤

第一步，确定数组中的最大值及其索引。假设数组为nums，则可以通过遍历数组找到最大值max_val及其索引max_index。这一过程对于后续递归至关重要。

第二步，创建当前节点。将最大值max_val作为当前节点的值，构建一个新节点node。

第三步，递归构造左子树和右子树。左子树由原数组中从起始位置到max_index-1的部分构成，右子树由从max_index+1到末尾的部分构成。通过递归调用构建子树，直到子数组为空。

三、C++代码实现

struct TreeNode { 
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}; 
TreeNode build(vector& nums, int start, int end) { 
    if (start > end) return NULL; 
    int max_index = start; 
    for (int i = start + 1; i <= end; ++i) if (nums[i] > nums[max_index]) max_index = i; 
    
    TreeNode node = new TreeNode(nums[max_index]);
    node->left = build(nums, start, max_index - 1); 
    node->right = build(nums, max_index +1, end); 
    return node; 
} 
TreeNode constructMaximumBinaryTree(vector& nums) { 
    return build(nums,0, nums.size() - 1); 
} 
void printTree(TreeNode root) { 
    if (!root) return; 
    cout << root->val << " "; 
    printTree(root->left); 
    printTree(root->right); 
} 
int main() { 
    vector nums = {3,2,1,6,0,5}; 
    TreeNode root = constructMaximumBinaryTree(nums); 
    printTree(root); 
    return 0; 
}

四、案例分析

以输入数组[3,2,1,6,0,5]为例，经过算法处理后，构建的最大二叉树为[6,3,5,null,2,0,null,null,1]。此结果表明，递归方法能够正确地找到数组中的最大值并构建相应的子树。通过对比输入数组与生成的二叉树结构，我们可以验证算法的正确性。最大二叉树的特性得到了充分体现，即每个节点的值都是其子树中的最大值。