leetcode108.将有序数组转换为二叉搜索树

目录 题目要求(一)分治法（递归）代码实现代码解释示例输入生成的平衡二叉搜索树结构中序遍历结果 复杂度分析总结 (二)栈（非递归）代码实现代码解释示例输入生成的平衡二叉搜索树结构中序遍历结果 复杂度分析总结

108. 将有序数组转换为二叉搜索树

题目要求

(一)分治法（递归）

要将一个升序排列的整数数组转换为一棵平衡的二叉搜索树（BST），我们可以采用 分治法。具体思路是：

找到数组的中间元素，将其作为树的根节点。递归处理左半部分数组，构建左子树。递归处理右半部分数组，构建右子树。

这种方法可以确保生成的二叉搜索树是平衡的，因为每次递归都选择中间元素作为根节点，左右子树的节点数相差不超过 1。

以下是 JavaScript 的实现代码：

代码实现 function TreeNode(val, left, right) { this.val = (val === undefined ? 0 : val); this.left = (left === undefined ? null : left); this.right = (right === undefined ? null : right); } function sortedArrayToBST(nums) { // 递归函数：构建平衡二叉搜索树 const buildTree = (left, right) => { if (left > right) { return null; // 递归终止条件 } // 找到中间元素作为根节点 const mid = Math.floor((left + right) / 2); const root = new TreeNode(nums[mid]); // 递归构建左子树和右子树 root.left = buildTree(left, mid - 1); root.right = buildTree(mid + 1, right); return root; }; return buildTree(0, nums.length - 1); } // 示例用法 const nums = [-10, -3, 0, 5, 9]; const bst = sortedArrayToBST(nums); // 打印树的结构（中序遍历） function inorderTraversal(root) { if (!root) return []; return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]; } console.log(inorderTraversal(bst)); // 输出: [-10, -3, 0, 5, 9]

---

代码解释

TreeNode 构造函数：

定义了二叉树的节点结构，包含 val、left 和 right。

sortedArrayToBST 函数：

主函数，接受一个升序数组 nums，返回平衡二叉搜索树的根节点。

buildTree 递归函数：

参数 left 和 right 表示当前子数组的左右边界。如果 left > right，说明当前子数组为空，返回 null。找到中间元素 nums[mid]，将其作为当前子树的根节点。递归构建左子树（left 到 mid - 1）和右子树（mid + 1 到 right）。

中序遍历验证：

使用 inorderTraversal 函数对生成的二叉搜索树进行中序遍历，确保结果与输入数组一致。

---

示例 输入 const nums = [-10, -3, 0, 5, 9]; 生成的平衡二叉搜索树结构 0 / \ -3 9 / / -10 5 中序遍历结果 [-10, -3, 0, 5, 9]

---

复杂度分析

时间复杂度：

每次递归都将数组分成两半，时间复杂度为 O(n)，其中 n 是数组的长度。

空间复杂度：

递归调用栈的深度为 O(log n)，因为树是平衡的。

---

总结

通过分治法，我们可以高效地将一个升序数组转换为平衡的二叉搜索树。这种方法的时间复杂度和空间复杂度都非常优秀，适合处理大规模数据。

---

(二)栈（非递归）

非递归方法也可以通过 迭代 和 栈 来实现将升序数组转换为平衡二叉搜索树。虽然递归方法更直观，但非递归方法可以避免递归调用栈的开销，适合处理深度较大的树。

以下是使用 栈 的非递归实现方法：

代码实现 function TreeNode(val, left, right) { this.val = (val === undefined ? 0 : val); this.left = (left === undefined ? null : left); this.right = (right === undefined ? null : right); } function sortedArrayToBST(nums) { if (nums.length === 0) return null; // 栈用于存储待处理的子数组范围及其父节点 const stack = []; const root = new TreeNode(); // 创建一个虚拟根节点 stack.push({ left: 0, right: nums.length - 1, parent: root, isLeft: true }); while (stack.length > 0) { const { left, right, parent, isLeft } = stack.pop(); if (left > right) { // 如果当前子数组为空，跳过 continue; } // 找到中间元素 const mid = Math.floor((left + right) / 2); const node = new TreeNode(nums[mid]); // 将当前节点挂到父节点上 if (isLeft) { parent.left = node; } else { parent.right = node; } // 将右半部分子数组和当前节点入栈 stack.push({ left: mid + 1, right: right, parent: node, isLeft: false }); // 将左半部分子数组和当前节点入栈 stack.push({ left: left, right: mid - 1, parent: node, isLeft: true }); } return root.left; // 返回真正的根节点 } // 示例用法 const nums = [-10, -3, 0, 5, 9]; const bst = sortedArrayToBST(nums); // 打印树的结构（中序遍历） function inorderTraversal(root) { if (!root) return []; return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]; } console.log(inorderTraversal(bst)); // 输出: [-10, -3, 0, 5, 9]

---

代码解释

栈的作用：

栈用于存储待处理的子数组范围及其父节点信息。每个栈元素包含： left 和 right：当前子数组的左右边界。parent：当前子数组的父节点。isLeft：当前子数组是父节点的左子树还是右子树。

初始化：

创建一个虚拟根节点 root，并将其与整个数组范围 [0, nums.length - 1] 入栈。

迭代过程：

从栈中弹出一个子数组范围及其父节点信息。如果 left > right，说明当前子数组为空，跳过。找到中间元素 nums[mid]，创建一个新节点。将新节点挂到父节点的左子树或右子树上（根据 isLeft 的值）。将右半部分子数组和当前节点入栈。将左半部分子数组和当前节点入栈。

返回结果：

最终返回虚拟根节点的左子树（即真正的根节点）。

---

示例 输入 const nums = [-10, -3, 0, 5, 9]; 生成的平衡二叉搜索树结构 0 / \ -3 9 / / -10 5 中序遍历结果 [-10, -3, 0, 5, 9]

---

复杂度分析

时间复杂度：

每个节点只会被处理一次，时间复杂度为 O(n)，其中 n 是数组的长度。

空间复杂度：

栈的最大深度为 O(log n)，因为树是平衡的。

---

总结

非递归方法通过栈模拟递归过程，避免了递归调用栈的开销，适合处理大规模数据或深度较大的树。虽然代码稍复杂，但性能更优。