【LeetCode刷题日记】108.将有序数组转换为二叉搜索树

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰又到了我们每日的刷题环节今天刷的题目是关于二叉搜索树的让我们一起来看看吧。题目背景108.将有序数组转换成二叉搜索树给你一个整数数组nums其中元素已经按升序排列请你将其转换为一棵 平衡 二叉搜索树。示例 1输入nums [-10,-3,0,5,9]输出[0,-3,9,-10,null,5]解释[0,-10,5,null,-3,null,9] 也将被视为正确答案示例 2输入nums [1,3]输出[3,1]解释[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。提示1 nums.length 104-104 nums[i] 104nums按严格递增顺序排列题目解析解题思路核心思想因为数组是有序的BST 的中序遍历就是升序序列。要构建高度平衡的 BST每次选择数组中间的元素作为根节点这样左右子树的元素个数相差不超过 1。递归步骤如果数组区间无效left right返回null找到中间位置mid left (right - left) / 2创建根节点new TreeNode(nums[mid])递归构建左子树root.left build(left, mid - 1)递归构建右子树root.right build(mid 1, right)返回根节点递归三部曲确定递归函数返回值及其参数删除二叉树节点增加二叉树节点都是用递归函数的返回值来完成这样是比较方便的。相信大家如果仔细看了前面的文章一定会对递归函数返回值的作用深有感触。那么本题要构造二叉树依然用递归函数的返回值来构造中节点的左右孩子。再来看参数首先是传入数组然后就是左下标left和右下标right我们在前面中提过在构造二叉树的时候尽量不要重新定义左右区间数组而是用下标来操作原数组。所以代码如下// 左闭右闭区间[left, right] TreeNode* traversal(vectorint nums, int left, int right)这里注意我这里定义的是左闭右闭区间在不断分割的过程中也会坚持左闭右闭的区间这又涉及到我们讲过的循环不变量。确定递归终止条件这里定义的是左闭右闭的区间所以当区间 left right的时候就是空节点了。代码如下if (left right) return nullptr;确定单层递归的逻辑首先取数组中间元素的位置不难写出int mid (left right) / 2;这么写其实有一个问题就是数值越界例如left和right都是最大int这么操作就越界了在二分法中尤其需要注意所以可以这么写int mid left ((right - left) / 2);直觉写法有bug大多数人第一反应是java int mid (left right) / 2;问题当left和right都很大时比如接近Integer.MAX_VALUEleft right可能会溢出变成负数导致mid计算错误。方法2安全写法防溢出java int mid left (right - left) / 2;推导过程text 目标求 left 和 right 的中点 (left right) / 2 left/2 right/2 left (right - left)/2 ← 变形验证假设left 4,right 10text 方式1(4 10) / 2 14 / 2 7 方式24 (10 - 4) / 2 4 6/2 4 3 7防溢出原理right - left最大值 ≈ 数组长度 ≤ 10^4不会溢出left 一个小数也不会溢出最后返回root节点单层递归整体代码如下int mid left ((right - left) / 2); TreeNode* root new TreeNode(nums[mid]); root-left traversal(nums, left, mid - 1); root-right traversal(nums, mid 1, right); return root;这里int mid left ((right - left) / 2);的写法相当于是如果数组长度为偶数中间位置有两个元素取靠左边的。图解示例输入nums [-10, -3, 0, 5, 9]构建过程text 第1步left0, right4, mid2, root0 0 / \ 左子树 右子树 [-10,-3] [5,9] 第2步左子树 left0, right1, mid0, root-10 0 / \ -10 右子树 \ -3 第2步右子树 left3, right4, mid3, root5 0 / \ -10 5 \ \ -3 9最终结果一种可能的平衡 BSTtext0 / \ -10 5 \ \ -3 9为什么这样构建是平衡的性质说明中间元素作根左右子树元素个数差 ≤ 1递归构建每个子树也都是平衡的BST 性质左子树所有值 根 右子树所有值因为数组升序复杂度分析时间复杂度O(n)每个节点只访问一次空间复杂度O(log n)递归栈深度平衡二叉树的高度多种中间点选择方式代码中int mid left (right - left) / 2选择的是左中位数。你也可以选择右中位数java // 右中位数数组长度为偶数时选靠右的 int mid left (right - left 1) / 2;不同的选择会产生不同形状的 BST但都是平衡的。例如[-10,-3,0,5,9]中间点选择根节点左中位数 (index 2)0右中位数 (index 3)5题目答案递归法class Solution { public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int left, int right) { // 递归终止条件 if (left right) { return null; } // 选择中间元素作为根节点 int mid left (right - left) / 2; TreeNode root new TreeNode(nums[mid]); // 递归构建左右子树 root.left build(nums, left, mid - 1); root.right build(nums, mid 1, right); return root; } }迭代法class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums.length 0) return null; //根节点初始化 TreeNode root new TreeNode(-1); QueueTreeNode nodeQueue new LinkedList(); QueueInteger leftQueue new LinkedList(); QueueInteger rightQueue new LinkedList(); // 根节点入队列 nodeQueue.offer(root); // 0为左区间下标初始位置 leftQueue.offer(0); // nums.size() - 1为右区间下标初始位置 rightQueue.offer(nums.length - 1); while (!nodeQueue.isEmpty()) { TreeNode currNode nodeQueue.poll(); int left leftQueue.poll(); int right rightQueue.poll(); int mid left ((right - left) 1); // 将mid对应的元素给中间节点 currNode.val nums[mid]; // 处理左区间 if (left mid - 1) { currNode.left new TreeNode(-1); nodeQueue.offer(currNode.left); leftQueue.offer(left); rightQueue.offer(mid - 1); } // 处理右区间 if (right mid 1) { currNode.right new TreeNode(-1); nodeQueue.offer(currNode.right); leftQueue.offer(mid 1); rightQueue.offer(right); } } return root; } }