当前位置：首页 > ops >正文

leetcode654.最大二叉树：递归分治下的最大值索引定位与树构建

ops 2025/7/28 19:01:45

一、题目深度解析与核心定义

题目描述

最大二叉树是一种特殊的二叉树结构，其定义为：

根节点是数组中的最大值
左子树是由最大值左边的子数组构建的最大二叉树
右子树是由最大值右边的子数组构建的最大二叉树

题目要求我们根据给定的整数数组，构建出对应的最大二叉树。例如，输入数组[3,2,1,6,0,5]，构建的最大二叉树如下：

      6/ \3   5\    \2    0\1

核心难点

最大值定位：每次递归需要快速找到子数组中的最大值及其索引
分治策略：根据最大值索引将数组分割为左右子数组，递归构建子树
边界处理：正确处理子数组为空或只有一个元素的情况

二、递归解法的核心实现与逻辑框架

完整递归代码实现

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return findMaxTree(nums, 0, nums.length);}public TreeNode findMaxTree(int[] nums, int numBegin, int numEnd) {// 终止条件1：子数组长度为0，返回nullif (numEnd - numBegin < 1) {return null;}// 终止条件2：子数组长度为1，直接创建节点if (numEnd - numBegin == 1) {return new TreeNode(nums[numBegin]);}// 寻找子数组中的最大值及其索引int maxIndex = numBegin;int maxVal = nums[numBegin];for (int i = numBegin + 1; i < numEnd; i++) {if (nums[i] > maxVal) {maxVal = nums[i];maxIndex = i;}}// 创建根节点（最大值）TreeNode root = new TreeNode(maxVal);// 递归构建左子树（最大值左边的子数组）root.left = findMaxTree(nums, numBegin, maxIndex);// 递归构建右子树（最大值右边的子数组）root.right = findMaxTree(nums, maxIndex + 1, numEnd);return root;}
}

核心设计解析：

递归函数参数：
- nums：原始数组
- numBegin/numEnd：当前处理的子数组左右边界（左闭右开）
- 意义：通过索引范围避免数组拷贝，高效划分递归子问题
最大值索引定位：
- 遍历子数组[numBegin, numEnd)寻找最大值
- 记录最大值maxVal和其索引maxIndex
- 时间复杂度：O(n) per递归层
树节点创建：
- 以最大值创建根节点
- 左子树由[numBegin, maxIndex)构建
- 右子树由[maxIndex+1, numEnd)构建

三、核心问题解析：递归中的最大值定位与分治逻辑

1. 最大值索引的定位逻辑

遍历寻找最大值

int maxIndex = numBegin;
int maxVal = nums[numBegin];
for (int i = numBegin + 1; i < numEnd; i++) {if (nums[i] > maxVal) {maxVal = nums[i];maxIndex = i;}
}

遍历范围：从numBegin到numEnd-1
更新策略：遇到更大值时更新maxVal和maxIndex
关键作用：确定当前子数组的根节点位置，分割左右子数组

示例说明：

数组[3,2,1,6,0,5]的完整数组范围是[0,6)
遍历找到最大值6，索引3，作为根节点
左子数组是[0,3)即[3,2,1]，右子数组是[4,6)即[0,5]

2. 递归分治的实现

递归终止条件

if (numEnd - numBegin < 1) return null;
if (numEnd - numBegin == 1) return new TreeNode(nums[numBegin]);

空数组处理：numEnd - numBegin < 1时返回null
单元素处理：直接创建节点，作为叶子节点
递归出口：确保递归能够正确终止

左右子树的递归构建

root.left = findMaxTree(nums, numBegin, maxIndex);
root.right = findMaxTree(nums, maxIndex + 1, numEnd);

左子树范围：从numBegin到maxIndex（左闭右开）
右子树范围：从maxIndex+1到numEnd（左闭右开）
分治思想：将原问题分解为两个规模更小的子问题

四、递归流程深度模拟：以示例数组为例

示例数组：`[3,2,1,6,0,5]`

递归构建过程：

第一次调用（构建整棵树）：
- 范围numBegin=0, numEnd=6
- 找到最大值6，索引3
- 创建根节点6，左子树范围[0,3)，右子树范围[4,6)
构建左子树（范围[0,3]，数组[3,2,1]）：
- 找到最大值3，索引0
- 创建节点3，左子树范围[0,0)（空），右子树范围[1,3)（数组[2,1]）
构建节点3的右子树（范围[1,3]，数组[2,1]）：
- 找到最大值2，索引1
- 创建节点2，左子树范围[1,1)（空），右子树范围[2,3)（数组[1]）
构建节点2的右子树（范围[2,3]，数组[1]）：
- 单元素，创建节点1，左右子树为空
构建根节点6的右子树（范围[4,6]，数组[0,5]）：
- 找到最大值5，索引5
- 创建节点5，左子树范围[4,5)（数组[0]），右子树范围[6,6)（空）
构建节点5的左子树（范围[4,5]，数组[0]）：
- 单元素，创建节点0，左右子树为空