【LeetCode刷题日记】654.最大二叉树：递归算法详解

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰又来到了每日的刷题时间学习的还是二叉树的相关知识和我们前面学的二叉树的构建差不多让我们一起看看吧。摘要本文介绍了如何构建最大二叉树的算法。给定一个不重复的整数数组通过递归方式构建二叉树首先找到当前数组片段的最大值作为根节点然后递归地在最大值左侧子数组构建左子树在右侧子数组构建右子树。文章详细解析了递归构建过程包括确定根节点、分割左右子数组、终止条件等关键步骤并通过示例演示了构建过程。最后提供了Java实现代码强调返回值在递归连接中的重要性。该算法采用前序遍历方式时间复杂度为O(n^2)适用于构建具有特定结构的二叉树。题目背景654.最大二叉树给定一个不重复的整数数组nums。最大二叉树可以用下面的算法从nums递归地构建:创建一个根节点其值为nums中的最大值。递归地在最大值左边的子数组前缀上构建左子树。递归地在最大值右边的子数组后缀上构建右子树。返回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 10000 nums[i] 1000nums中的所有整数互不相同题目分析我们拿到这个题目就能知道这是个二叉树的构建问题正如题目所说的最大二叉树需要根据一定的规则来构建。根据题目要求我们要先构建根节点从这里我们就可以知道我们要用前序遍历的方式来构建这个根节点就是当前数组的最大值之后根据题目要求这个数组由最大值为中间节点将数组划分为左右两部分然后继续构建最大二叉树以此类推其实我们看出来这就是递归的思维。核心思路解析确定根节点在当前的数组片段中最大值就是这棵子树的根节点。分割左右最大值左边的区间用来递归构建左子树。最大值右边的区间用来递归构建右子树。终止条件当递归的起始索引left大于结束索引right时说明没有元素了返回null第一步肯定就是找到数组的最大值很容易实现需要注意的是我们也需要找到最大值的索引为了后续的数组划分。第二步就是创建根节点然后依次递归很简单的思路。举个例子假设nums [3,2,1,6,0,5]第一次调用构建整棵树javabuild(nums, 0, 5) // left0, right5在[0,5]范围内找到最大值6在索引3所以根节点 6左子树范围[0, 2]6左边的元素3,2,1右子树范围[4, 5]6右边的元素0,5关键来了javaroot.left build(nums, 0, 2); // 用左边部分递归构建左子树 root.right build(nums, 4, 5); // 用右边部分递归构建右子树递归构建左子树build(nums, 0, 2)现在处理[0,2]范围即[3,2,1]找到最大值3在索引0根节点 3左子树范围[0, -1]3左边没有元素右子树范围[1, 2]3右边2,1javaroot.left build(nums, 0, -1); // left right返回 null root.right build(nums, 1, 2); // 继续构建子树图解整个过程text原始数组: [3, 2, 1, 6, 0, 5] ↑ 最大值6在第3位 步骤1: 6 / \ 左边[3,2,1] 右边[0,5] 步骤2: 处理左边 6 / \ 3 [0,5]待处理 / \ null [2,1]待处理 步骤3: 继续...最终得到: 6 / \ 3 5 \ / 2 0 \ 1易错分析为什么参数是maxIndex - 1和maxIndex 1因为最大值作为根节点后左子树应该使用最大值左边的所有元素左边元素的索引范围是[left, maxIndex - 1]右子树应该使用最大值右边的所有元素右边元素的索引范围是[maxIndex 1, right]这样就能确保左子树只用左边的元素构建右子树只用右边的元素构建不会重复使用最大值本身关于方法的返回值我们从栈的角度来理解// 第一次调用 build(0,5) TreeNode root new TreeNode(6); // 在栈帧1中创建节点6 root.left build(0,2); // 调用栈帧2等待返回值 // 进入栈帧2 // 第二次调用 build(0,2) - 完全独立的方法调用 TreeNode root new TreeNode(3); // 在栈帧2中创建节点3不同的root变量 root.right build(1,2); // 调用栈帧3等待返回值 // 进入栈帧3 // 第三次调用 build(1,2) TreeNode root new TreeNode(2); // 在栈帧3中创建节点2 root.right build(2,2); // 调用栈帧4 // 进入栈帧4 // 第四次调用 build(2,2) TreeNode root new TreeNode(1); // 在栈帧4中创建节点1 return root; // 返回节点1给栈帧3 // 回到栈帧3 // 现在栈帧3得到了返回值 root.right 节点1; // 栈帧3的root节点2的right指向节点1 return root; // 返回节点2给栈帧2 // 回到栈帧2 root.right 节点2; // 栈帧2的root节点3的right指向节点2 return root; // 返回节点3给栈帧1 // 回到栈帧1 root.left 节点3; // 栈帧1的root节点6的left指向节点3 return root; // 返回节点6给main如果没有返回值无法建立连接上一层无法拿到当前层创建的节点节点丢失创建的节点只在当前方法内有效方法结束后就丢失了返回根节点的三个必要性递归需要父节点需要子节点返回的值来建立left/right连接调用者需要main方法力扣系统需要根节点来验证答案数据不丢失Java方法内的局部变量在方法结束后会销毁必须通过返回值传递出去题目答案/** * 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 build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int left, int right) { // 递归终止条件区间无效返回空节点 if (left right) { return null; } // 1. 在当前区间 [left, right] 中找到最大值及其索引 int maxIndex left; for (int i left 1; i right; i) { if (nums[i] nums[maxIndex]) { maxIndex i; } } // 2. 创建根节点 TreeNode root new TreeNode(nums[maxIndex]); // 3. 递归构建左子树最大值左边的部分 root.left build(nums, left, maxIndex - 1); // 4. 递归构建右子树最大值右边的部分 root.right build(nums, maxIndex 1, right); return root; } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励