尧图网站建设 
有序数组转高度平衡二叉搜索树LeetCode 108 的三种 DFS 解法与多语言实现详解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以仓库文档 articles/convert-sorted-array-to-binary-search-tree.md 为主体骨架系统讲解如何将升序数组转换为高度平衡二叉搜索树BST从朴素递归切片、索引边界递归到迭代 DFS 三种由浅入深的做法并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整代码与复杂度分析。同时结合本仓库0108-convert-sorted-array-to-binary-search-tree系列源码python、java、go、javascript、kotlin、c 六种实现进行佐证帮助读者彻底吃透这一经典的分治递归问题并能在实际编码中规避 off-by-one 等典型陷阱。问题背景与前置知识该问题对应 LeetCode 108Convert Sorted Array to Binary Search Tree给定一个按升序排列的整数数组nums将其转换为一棵高度平衡的二叉搜索树。所谓高度平衡是指对于树中每一个节点其左右子树的高度差绝对值不超过 1。在动手编码之前需要先具备以下三项基础能力二叉搜索树BST理解 BST 的性质——左子树所有节点的值小于根节点右子树所有节点的值大于根节点。这一性质是排序数组天然适合建 BST的根本原因数组的中位数恰好可以充当根节点使左右两侧元素数量均衡。递归Recursion把大问题拆成结构相同的子问题。建树过程中每个子树都是取一段有序子数组的中间元素作根这一相同模式的重复。分治Divide and Conquer每次在数组中间位置切分中位数为根左右两半分别递归构建左右子树从而天然保证平衡。仓库中的 C 实现 c/0108-convert-sorted-array-to-binary-search-tree.c 在注释中直接点明了本问题的核心约束Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree并标注了整体复杂度Space: O(n), Time: O(n)可作为后续三种解法的目标基准。解法一朴素递归数组切片版 DFS直觉要从有序数组构建高度平衡 BST关键在于保证每个节点的左右子树高度大致相等。由于数组已经有序中间元素天然应该成为根中间元素之前的所有元素进入左子树之后的所有元素进入右子树。递归地应用这一规则就能构建出一棵平衡树。算法步骤基准情形如果当前数组段为空返回null。计算当前数组段的中间下标。以中间元素的值创建新的树节点。用中间元素左侧的子数组递归构建左子树。用中间元素右侧的子数组递归构建右子树。返回根节点。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]: if not nums: return None mid len(nums) // 2 root TreeNode(nums[mid]) root.left self.sortedArrayToBST(nums[:mid]) root.right self.sortedArrayToBST(nums[mid 1:]) return root/** * 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; * } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums.length 0) { return null; } int mid nums.length / 2; TreeNode root new TreeNode(nums[mid]); root.left sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid)); root.right sortedArrayToBST(Arrays.copyOfRange(nums, mid 1, nums.length)); return root; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { if (nums.empty()) { return nullptr; } int mid nums.size() / 2; TreeNode* root new TreeNode(nums[mid]); vectorint left(nums.begin(), nums.begin() mid); vectorint right(nums.begin() mid 1, nums.end()); root-left sortedArrayToBST(left); root-right sortedArrayToBST(right); return root; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {number[]} nums * return {TreeNode} */ sortedArrayToBST(nums) { if (nums.length 0) { return null; } const mid Math.floor(nums.length / 2); const root new TreeNode(nums[mid]); root.left this.sortedArrayToBST(nums.slice(0, mid)); root.right this.sortedArrayToBST(nums.slice(mid 1)); return root; } }/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public TreeNode SortedArrayToBST(int[] nums) { if (nums.Length 0) { return null; } int mid nums.Length / 2; TreeNode root new TreeNode(nums[mid]); root.left SortedArrayToBST(nums.Take(mid).ToArray()); root.right SortedArrayToBST(nums.Skip(mid 1).ToArray()); return root; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sortedArrayToBST(nums []int) *TreeNode { if len(nums) 0 { return nil } mid : len(nums) / 2 root : TreeNode{Val: nums[mid]} root.Left sortedArrayToBST(nums[:mid]) root.Right sortedArrayToBST(nums[mid1:]) return root }/** * Definition for a binary tree node. * class TreeNode(var val: Int 0) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { if (nums.isEmpty()) { return null } val mid nums.size / 2 val root TreeNode(nums[mid]) root.left sortedArrayToBST(nums.sliceArray(0 until mid)) root.right sortedArrayToBST(nums.sliceArray(mid 1 until nums.size)) return root } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func sortedArrayToBST(_ nums: [Int]) - TreeNode? { if nums.isEmpty { return nil } let mid nums.count / 2 let root TreeNode(nums[mid]) root.left sortedArrayToBST(Array(nums[0..mid])) root.right sortedArrayToBST(Array(nums[(mid 1)...])) return root } }// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn sorted_array_to_bst(nums: Veci32) - OptionRcRefCellTreeNode { if nums.is_empty() { return None; } let mid nums.len() / 2; let mut root TreeNode::new(nums[mid]); root.left Self::sorted_array_to_bst(nums[..mid].to_vec()); root.right Self::sorted_array_to_bst(nums[mid 1..].to_vec()); Some(Rc::new(RefCell::new(root))) } }复杂度分析时间复杂度$O(n \log n)$空间复杂度$O(n)$需要说明的是这里的 $O(n \log n)$ 来源于每次递归调用都要复制子数组如 Python 的nums[:mid]、Java 的Arrays.copyOfRange、C 的vector拷贝每一层总共复制 $O(n)$ 个元素递归树深度为 $O(\log n)$故总时间为 $O(n \log n)$。仓库源码佐证本仓库中的 Python 与 Go 实现采用了这一切片思路。以 python/0108-convert-sorted-array-to-binary-search-tree.py 为例class Solution: def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]: if not nums: return None mid len(nums)//2 root TreeNode(nums[mid]) root.left self.sortedArrayToBST(nums[:mid]) root.right self.sortedArrayToBST(nums[mid1:]) return rootgo/0108-convert-sorted-array-to-binary-search-tree.go 的结构与之完全一致额外在入口处对nums nil的空切片做了防御func sortedArrayToBST(nums []int) *TreeNode { if nums nil || len(nums) 0 { return nil } mid : len(nums) / 2 return TreeNode{ Val: nums[mid], Left: sortedArrayToBST(nums[:mid]), Right: sortedArrayToBST(nums[mid1:]), } }从实现上看Python 的切片是拷贝新列表因此该方法在 Python 中符合 $O(n \log n)$ 的复杂度结论而 Go 的切片nums[:mid]是对底层数组的视图、不拷贝数据其常数开销更低——这是一个值得注意的语言差异。解法二索引边界递归最优 DFS直觉上面的方法每次递归都创建新的数组副本效率偏低。更优的做法是直接传入left和right两个边界下标来标识当前处理的数组段彻底避免数组切片。这样既维持了取中间元素为根的核心逻辑又显著降低了时间和空间开销。算法步骤定义一个接收left、right边界下标的辅助函数。基准情形若left right说明当前段为空返回null。计算中间下标(left right) / 2。以中间下标的元素值创建树节点。用边界(left, mid - 1)递归构建左子树。用边界(mid 1, right)递归构建右子树。以初始边界(0, n - 1)调用辅助函数并返回结果。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def sortedArrayToBST(self, nums: List[int]) - TreeNode: def helper(l, r): if l r: return None m (l r) // 2 root TreeNode(nums[m]) root.left helper(l, m - 1) root.right helper(m 1, r) return root return helper(0, len(nums) - 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; * } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums, 0, nums.length - 1); } private TreeNode helper(int[] nums, int l, int r) { if (l r) { return null; } int m (l r) / 2; TreeNode root new TreeNode(nums[m]); root.left helper(nums, l, m - 1); root.right helper(nums, m 1, r); return root; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { return helper(nums, 0, nums.size() - 1); } private: TreeNode* helper(vectorint nums, int l, int r) { if (l r) { return nullptr; } int m (l r) / 2; TreeNode* root new TreeNode(nums[m]); root-left helper(nums, l, m - 1); root-right helper(nums, m 1, r); return root; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {number[]} nums * return {TreeNode} */ sortedArrayToBST(nums) { const helper (l, r) { if (l r) { return null; } const m Math.floor((l r) / 2); const root new TreeNode(nums[m]); root.left helper(l, m - 1); root.right helper(m 1, r); return root; }; return helper(0, nums.length - 1); } }/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public TreeNode SortedArrayToBST(int[] nums) { return Helper(nums, 0, nums.Length - 1); } private TreeNode Helper(int[] nums, int l, int r) { if (l r) { return null; } int m (l r) / 2; TreeNode root new TreeNode(nums[m]); root.left Helper(nums, l, m - 1); root.right Helper(nums, m 1, r); return root; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sortedArrayToBST(nums []int) *TreeNode { var helper func(l, r int) *TreeNode helper func(l, r int) *TreeNode { if l r { return nil } m : (l r) / 2 root : TreeNode{Val: nums[m]} root.Left helper(l, m-1) root.Right helper(m1, r) return root } return helper(0, len(nums)-1) }/** * Definition for a binary tree node. * class TreeNode(var val: Int 0) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { fun helper(l: Int, r: Int): TreeNode? { if (l r) { return null } val m (l r) / 2 val root TreeNode(nums[m]) root.left helper(l, m - 1) root.right helper(m 1, r) return root } return helper(0, nums.size - 1) } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func sortedArrayToBST(_ nums: [Int]) - TreeNode? { func helper(_ l: Int, _ r: Int) - TreeNode? { if l r { return nil } let m (l r) / 2 let root TreeNode(nums[m]) root.left helper(l, m - 1) root.right helper(m 1, r) return root } return helper(0, nums.count - 1) } }impl Solution { pub fn sorted_array_to_bst(nums: Veci32) - OptionRcRefCellTreeNode { fn helper(nums: [i32], l: i32, r: i32) - OptionRcRefCellTreeNode { if l r { return None; } let m (l r) / 2; let mut root TreeNode::new(nums[m as usize]); root.left helper(nums, l, m - 1); root.right helper(nums, m 1, r); Some(Rc::new(RefCell::new(root))) } helper(nums, 0, nums.len() as i32 - 1) } }复杂度分析时间复杂度$O(n)$每个元素恰好被访问一次创建 $n$ 个节点无复制开销空间复杂度递归调用栈 $O(\log n)$平衡树高度为 $\log n$输出树本身占用 $O(n)$仓库源码佐证索引边界版正是仓库中多数语言提交的实现。以 java/0108-convert-sorted-array-to-binary-search-tree.java 为例它把辅助函数命名为generateTree并采用了一个非常值得借鉴的细节——防溢出写法class Solution { public TreeNode sortedArrayToBST(int[] nums) { return generateTree(nums, 0, nums.length - 1); } public TreeNode generateTree(int[] nums, int low, int high) { if (low high) { return null; } int mid low ((high - low) / 2); TreeNode node new TreeNode(nums[mid]); node.left generateTree(nums, low, mid - 1); node.right generateTree(nums, mid 1, high); return node; } }注意第 11 行使用的是low ((high - low) / 2)而非(low high) / 2。当low high超过int上限时后者可能发生整数溢出而前者可以完全规避——这是生产代码中常见的防御性写法也是面试中容易加分的细节。c/0108-convert-sorted-array-to-binary-search-tree.c 采用了同样的边界递归思路并将辅助函数命名为dichomoty_rec二分递归同时用malloc手动分配节点内存struct TreeNode* dichomoty_rec(int* nums, int i, int j) { if (ij) return NULL; struct TreeNode* new_t malloc(sizeof(struct TreeNode)); int m (ij)/2; new_t-val nums[m]; new_t-left dichomoty_rec(nums, i, m-1); new_t-right dichomoty_rec(nums, m1, j); return new_t; } struct TreeNode* sortedArrayToBST(int* nums, int numsSize){ return dichomoty_rec(nums, 0, numsSize-1); }kotlin/0108-convert-sorted-array-to-binary-search-tree.kt 的实现还额外做了一层微优化当left right区间只剩一个元素时直接返回叶子节点省去一次多余的中间下标计算与递归展开class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { fun createTree(left: Int, right: Int): TreeNode? { if(left right) return null else if(left right) return TreeNode(nums[left]) val mid (left right) / 2 val node TreeNode(nums[mid]) node.left createTree(left, mid-1) node.right createTree(mid1, right) return node } return createTree(0, nums.lastIndex) } }解法三迭代 DFS显式栈直觉递归解法本质上依赖系统调用栈我们可以用显式栈将其改写成迭代形式。栈中存放待处理的工作项每个工作项包含一个待填充的节点以及它对应的数组边界。这样便模拟了递归调用栈的行为无需系统递归即可逐个子树处理从而彻底规避深递归可能导致的栈溢出风险。算法步骤若数组为空返回null。创建一个占位值的根节点。将根节点及其边界(0, n-1)压入栈。当栈非空时循环弹出包含节点及其边界(l, r)的工作项。计算中间下标将节点值设为nums[mid]。若左侧还有元素l mid - 1创建左孩子并入栈边界为(l, mid - 1)。若右侧还有元素mid 1 r创建右孩子并入栈边界为(mid 1, r)。返回根节点。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def sortedArrayToBST(self, nums: List[int]) - TreeNode: if not nums: return None root TreeNode(0) stack [(root, 0, len(nums) - 1)] while stack: node, l, r stack.pop() m (l r) // 2 node.val nums[m] if l m - 1: node.left TreeNode(0) stack.append((node.left, l, m - 1)) if m 1 r: node.right TreeNode(0) stack.append((node.right, m 1, r)) return root/** * 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; * } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums.length 0) { return null; } TreeNode root new TreeNode(0); Stackint[] stack new Stack(); StackTreeNode nodes new Stack(); stack.push(new int[]{0, nums.length - 1}); nodes.push(root); while (!stack.isEmpty()) { int[] range stack.pop(); TreeNode node nodes.pop(); int l range[0], r range[1]; int m (l r) / 2; node.val nums[m]; if (l m - 1) { node.left new TreeNode(0); stack.push(new int[]{l, m - 1}); nodes.push(node.left); } if (m 1 r) { node.right new TreeNode(0); stack.push(new int[]{m 1, r}); nodes.push(node.right); } } return root; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { if (nums.empty()) return nullptr; TreeNode* root new TreeNode(0); stacktupleTreeNode*, int, int stack; stack.push({root, 0, (int)nums.size() - 1}); while (!stack.empty()) { auto [node, l, r] stack.top(); stack.pop(); int m (l r) / 2; node-val nums[m]; if (l m - 1) { node-left new TreeNode(0); stack.push({node-left, l, m - 1}); } if (m 1 r) { node-right new TreeNode(0); stack.push({node-right, m 1, r}); } } return root; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {number[]} nums * return {TreeNode} */ sortedArrayToBST(nums) { if (nums.length 0) { return null; } const root new TreeNode(0); const stack [[root, 0, nums.length - 1]]; while (stack.length) { const [node, l, r] stack.pop(); const m Math.floor((l r) / 2); node.val nums[m]; if (l m - 1) { node.left new TreeNode(0); stack.push([node.left, l, m - 1]); } if (m 1 r) { node.right new TreeNode(0); stack.push([node.right, m 1, r]); } } return root; } }/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public TreeNode SortedArrayToBST(int[] nums) { if (nums.Length 0) { return null; } TreeNode root new TreeNode(0); Stack(TreeNode, int, int) stack new Stack(TreeNode, int, int)(); stack.Push((root, 0, nums.Length - 1)); while (stack.Count 0) { var (node, l, r) stack.Pop(); int m (l r) / 2; node.val nums[m]; if (l m - 1) { node.left new TreeNode(0); stack.Push((node.left, l, m - 1)); } if (m 1 r) { node.right new TreeNode(0); stack.Push((node.right, m 1, r)); } } return root; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sortedArrayToBST(nums []int) *TreeNode { if len(nums) 0 { return nil } type item struct { node *TreeNode l, r int } root : TreeNode{Val: 0} stack : []item{{root, 0, len(nums) - 1}} for len(stack) 0 { curr : stack[len(stack)-1] stack stack[:len(stack)-1] m : (curr.l curr.r) / 2 curr.node.Val nums[m] if curr.l m-1 { curr.node.Left TreeNode{Val: 0} stack append(stack, item{curr.node.Left, curr.l, m - 1}) } if m1 curr.r { curr.node.Right TreeNode{Val: 0} stack append(stack, item{curr.node.Right, m 1, curr.r}) } } return root }/** * Definition for a binary tree node. * class TreeNode(var val: Int 0) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { if (nums.isEmpty()) { return null } val root TreeNode(0) val stack ArrayDequeTripleTreeNode, Int, Int() stack.addLast(Triple(root, 0, nums.size - 1)) while (stack.isNotEmpty()) { val (node, l, r) stack.removeLast() val m (l r) / 2 node.val nums[m] if (l m - 1) { node.left TreeNode(0) stack.addLast(Triple(node.left!!, l, m - 1)) } if (m 1 r) { node.right TreeNode(0) stack.addLast(Triple(node.right!!, m 1, r)) } } return root } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func sortedArrayToBST(_ nums: [Int]) - TreeNode? { if nums.isEmpty { return nil } let root TreeNode(0) var stack: [(TreeNode, Int, Int)] [(root, 0, nums.count - 1)] while !stack.isEmpty { let (node, l, r) stack.removeLast() let m (l r) / 2 node.val nums[m] if l m - 1 { node.left TreeNode(0) stack.append((node.left!, l, m - 1)) } if m 1 r { node.right TreeNode(0) stack.append((node.right!, m 1, r)) } } return root } }impl Solution { pub fn sorted_array_to_bst(nums: Veci32) - OptionRcRefCellTreeNode { if nums.is_empty() { return None; } let root Rc::new(RefCell::new(TreeNode::new(0))); let mut stack: Vec(RcRefCellTreeNode, usize, usize) vec![(Rc::clone(root), 0, nums.len() - 1)]; while let Some((node, l, r)) stack.pop() { let m (l r) / 2; node.borrow_mut().val nums[m]; if l m { let left Rc::new(RefCell::new(TreeNode::new(0))); node.borrow_mut().left Some(Rc::clone(left)); stack.push((left, l, m - 1)); } if m 1 r { let right Rc::new(RefCell::new(TreeNode::new(0))); node.borrow_mut().right Some(Rc::clone(right)); stack.push((right, m 1, r)); } } Some(root) } }复杂度分析时间复杂度$O(n)$每个元素仍只被处理一次空间复杂度显式栈最多同时存放 $O(\log n)$ 个工作项输出树本身占用 $O(n)$迭代版与前两种递归版在渐进复杂度上一致其价值在于不消耗系统调用栈。在数组规模极大递归深度达 $\log n$ 通常可控或运行环境栈空间受限的嵌入式/低资源场景下迭代 DFS 是更稳妥的选择。常见陷阱陷阱一子数组边界的 Off-by-One 错误递归构建子树时最常见的错误是把中间元素也包含进某一侧的子树导致无限递归或节点重复。# 错误 - 左子树错误地包含了 mid root.left helper(l, m) # 应该为 m - 1 # 正确 root.left helper(l, m - 1) root.right helper(m 1, r)判断标准很简单根节点已经取了nums[mid]那么左边界段必须是[l, mid-1]右边界段必须是[mid1, r]三者合起来恰好覆盖完整区间且互不重叠。对照三种解法可见切片版用nums[:mid]与nums[mid1:]天然排除了mid边界版用helper(l, m - 1)与helper(m 1, r)显式排除迭代版则用l m - 1与m 1 r两个条件守卫——它们遵守的是同一条不变式。陷阱二偶数长度数组的中间元素选择不一致对于长度为偶数的数组中间元素可以取(l r) // 2左中位也可以取(l r 1) // 2右中位。两种选择都能构造出合法的高度平衡 BST但若在同一份代码里混用会造成结果的不一致与调试困难。题目本身接受任意一种选择关键是始终如一地使用同一种约定。仓库中的 javascript/0108-convert-sorted-array-to-binary-search-tree.js 恰好给出了这个讨论的三种实证变体注释分别为DFS - Preorder | Left as mid、DFS - Preorder | Right as mid、DFS - Preorder | Random as mid左中位版const mid (left right) 1;与Math.floor((l r) / 2)等价右中位版当(left right)为奇数时mid 1即取(l r 1) // 2随机中位版奇数时mid Math.floor(Math.random() * 2)随机取左中位或右中位三者均标注Time O(N) | Space O(log(N))从实现层面印证了任选其一皆可、保持一致即可的结论。面试中推荐固定使用左中位(l r) // 2因为它与多数语言的默认整除语义一致最不易出错。三种解法对比与仓库实现一览解法核心思路时间复杂度空间复杂度适用场景解法一递归 数组切片每层复制子数组取中点为根$O(n \log n)$$O(n)$代码最直观适合快速演示分治思想输入规模小时无碍解法二递归 索引边界用(l, r)边界避免复制$O(n)$$O(\log n)$栈 $O(n)$输出面试/生产首选兼顾简洁与效率解法三迭代 显式栈用显式栈模拟递归$O(n)$$O(\log n)$栈 $O(n)$输出需要规避系统调用栈开销的场景本仓库为该题提供的多语言源码清单均可作为可运行、可验证的参考实现python/0108-convert-sorted-array-to-binary-search-tree.py解法一切片版go/0108-convert-sorted-array-to-binary-search-tree.go解法一切片版含空切片防御java/0108-convert-sorted-array-to-binary-search-tree.java解法二索引版含防溢出取中写法kotlin/0108-convert-sorted-array-to-binary-search-tree.kt解法二索引版含单元素早返回优化c/0108-convert-sorted-array-to-binary-search-tree.c解法二索引版C 语言malloc手动建树javascript/0108-convert-sorted-array-to-binary-search-tree.js解法二索引版附左中位/右中位/随机中位三种变体总结有序数组转高度平衡 BST是分治与递归思想的经典载体取中点为根、左右递归这一句话贯穿始终。掌握三条递进路径——朴素切片理解分治、索引边界消除复制开销、迭代栈摆脱系统递归配合对边界 off-by-one 与偶数长度取中约定的清醒认识就足以应对该题在任意面试变体中的考察。无论选择哪种解法最终产出的都是一棵中序遍历与升序数组严格对应、且高度为 $O(\log n)$ 的平衡 BST这正是有序数据在二叉搜索树中保持 $O(\log n)$ 查询性能的关键所在。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 有序数组转高度平衡二叉搜索树：LeetCode 108 的三种 DFS 解法与多语言实现详解
有序数组转高度平衡二叉搜索树LeetCode 108 的三种 DFS 解法与多语言实现详解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以仓库文档 articles/convert-sorted-array-to-binary-search-tree.md 为主体骨架系统讲解如何将升序数组转换为高度平衡二叉搜索树BST从朴素递归切片、索引边界递归到迭代 DFS 三种由浅入深的做法并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整代码与复杂度分析。同时结合本仓库0108-convert-sorted-array-to-binary-search-tree系列源码python、java、go、javascript、kotlin、c 六种实现进行佐证帮助读者彻底吃透这一经典的分治递归问题并能在实际编码中规避 off-by-one 等典型陷阱。问题背景与前置知识该问题对应 LeetCode 108Convert Sorted Array to Binary Search Tree给定一个按升序排列的整数数组nums将其转换为一棵高度平衡的二叉搜索树。所谓高度平衡是指对于树中每一个节点其左右子树的高度差绝对值不超过 1。在动手编码之前需要先具备以下三项基础能力二叉搜索树BST理解 BST 的性质——左子树所有节点的值小于根节点右子树所有节点的值大于根节点。这一性质是排序数组天然适合建 BST的根本原因数组的中位数恰好可以充当根节点使左右两侧元素数量均衡。递归Recursion把大问题拆成结构相同的子问题。建树过程中每个子树都是取一段有序子数组的中间元素作根这一相同模式的重复。分治Divide and Conquer每次在数组中间位置切分中位数为根左右两半分别递归构建左右子树从而天然保证平衡。仓库中的 C 实现 c/0108-convert-sorted-array-to-binary-search-tree.c 在注释中直接点明了本问题的核心约束Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree并标注了整体复杂度Space: O(n), Time: O(n)可作为后续三种解法的目标基准。解法一朴素递归数组切片版 DFS直觉要从有序数组构建高度平衡 BST关键在于保证每个节点的左右子树高度大致相等。由于数组已经有序中间元素天然应该成为根中间元素之前的所有元素进入左子树之后的所有元素进入右子树。递归地应用这一规则就能构建出一棵平衡树。算法步骤基准情形如果当前数组段为空返回null。计算当前数组段的中间下标。以中间元素的值创建新的树节点。用中间元素左侧的子数组递归构建左子树。用中间元素右侧的子数组递归构建右子树。返回根节点。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]: if not nums: return None mid len(nums) // 2 root TreeNode(nums[mid]) root.left self.sortedArrayToBST(nums[:mid]) root.right self.sortedArrayToBST(nums[mid 1:]) return root/** * 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; * } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums.length 0) { return null; } int mid nums.length / 2; TreeNode root new TreeNode(nums[mid]); root.left sortedArrayToBST(Arrays.copyOfRange(nums, 0, mid)); root.right sortedArrayToBST(Arrays.copyOfRange(nums, mid 1, nums.length)); return root; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { if (nums.empty()) { return nullptr; } int mid nums.size() / 2; TreeNode* root new TreeNode(nums[mid]); vectorint left(nums.begin(), nums.begin() mid); vectorint right(nums.begin() mid 1, nums.end()); root-left sortedArrayToBST(left); root-right sortedArrayToBST(right); return root; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {number[]} nums * return {TreeNode} */ sortedArrayToBST(nums) { if (nums.length 0) { return null; } const mid Math.floor(nums.length / 2); const root new TreeNode(nums[mid]); root.left this.sortedArrayToBST(nums.slice(0, mid)); root.right this.sortedArrayToBST(nums.slice(mid 1)); return root; } }/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public TreeNode SortedArrayToBST(int[] nums) { if (nums.Length 0) { return null; } int mid nums.Length / 2; TreeNode root new TreeNode(nums[mid]); root.left SortedArrayToBST(nums.Take(mid).ToArray()); root.right SortedArrayToBST(nums.Skip(mid 1).ToArray()); return root; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sortedArrayToBST(nums []int) *TreeNode { if len(nums) 0 { return nil } mid : len(nums) / 2 root : TreeNode{Val: nums[mid]} root.Left sortedArrayToBST(nums[:mid]) root.Right sortedArrayToBST(nums[mid1:]) return root }/** * Definition for a binary tree node. * class TreeNode(var val: Int 0) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { if (nums.isEmpty()) { return null } val mid nums.size / 2 val root TreeNode(nums[mid]) root.left sortedArrayToBST(nums.sliceArray(0 until mid)) root.right sortedArrayToBST(nums.sliceArray(mid 1 until nums.size)) return root } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func sortedArrayToBST(_ nums: [Int]) - TreeNode? { if nums.isEmpty { return nil } let mid nums.count / 2 let root TreeNode(nums[mid]) root.left sortedArrayToBST(Array(nums[0..mid])) root.right sortedArrayToBST(Array(nums[(mid 1)...])) return root } }// Definition for a binary tree node. // #[derive(Debug, PartialEq, Eq)] // pub struct TreeNode { // pub val: i32, // pub left: OptionRcRefCellTreeNode, // pub right: OptionRcRefCellTreeNode, // } impl Solution { pub fn sorted_array_to_bst(nums: Veci32) - OptionRcRefCellTreeNode { if nums.is_empty() { return None; } let mid nums.len() / 2; let mut root TreeNode::new(nums[mid]); root.left Self::sorted_array_to_bst(nums[..mid].to_vec()); root.right Self::sorted_array_to_bst(nums[mid 1..].to_vec()); Some(Rc::new(RefCell::new(root))) } }复杂度分析时间复杂度$O(n \log n)$空间复杂度$O(n)$需要说明的是这里的 $O(n \log n)$ 来源于每次递归调用都要复制子数组如 Python 的nums[:mid]、Java 的Arrays.copyOfRange、C 的vector拷贝每一层总共复制 $O(n)$ 个元素递归树深度为 $O(\log n)$故总时间为 $O(n \log n)$。仓库源码佐证本仓库中的 Python 与 Go 实现采用了这一切片思路。以 python/0108-convert-sorted-array-to-binary-search-tree.py 为例class Solution: def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]: if not nums: return None mid len(nums)//2 root TreeNode(nums[mid]) root.left self.sortedArrayToBST(nums[:mid]) root.right self.sortedArrayToBST(nums[mid1:]) return rootgo/0108-convert-sorted-array-to-binary-search-tree.go 的结构与之完全一致额外在入口处对nums nil的空切片做了防御func sortedArrayToBST(nums []int) *TreeNode { if nums nil || len(nums) 0 { return nil } mid : len(nums) / 2 return TreeNode{ Val: nums[mid], Left: sortedArrayToBST(nums[:mid]), Right: sortedArrayToBST(nums[mid1:]), } }从实现上看Python 的切片是拷贝新列表因此该方法在 Python 中符合 $O(n \log n)$ 的复杂度结论而 Go 的切片nums[:mid]是对底层数组的视图、不拷贝数据其常数开销更低——这是一个值得注意的语言差异。解法二索引边界递归最优 DFS直觉上面的方法每次递归都创建新的数组副本效率偏低。更优的做法是直接传入left和right两个边界下标来标识当前处理的数组段彻底避免数组切片。这样既维持了取中间元素为根的核心逻辑又显著降低了时间和空间开销。算法步骤定义一个接收left、right边界下标的辅助函数。基准情形若left right说明当前段为空返回null。计算中间下标(left right) / 2。以中间下标的元素值创建树节点。用边界(left, mid - 1)递归构建左子树。用边界(mid 1, right)递归构建右子树。以初始边界(0, n - 1)调用辅助函数并返回结果。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def sortedArrayToBST(self, nums: List[int]) - TreeNode: def helper(l, r): if l r: return None m (l r) // 2 root TreeNode(nums[m]) root.left helper(l, m - 1) root.right helper(m 1, r) return root return helper(0, len(nums) - 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; * } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { return helper(nums, 0, nums.length - 1); } private TreeNode helper(int[] nums, int l, int r) { if (l r) { return null; } int m (l r) / 2; TreeNode root new TreeNode(nums[m]); root.left helper(nums, l, m - 1); root.right helper(nums, m 1, r); return root; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { return helper(nums, 0, nums.size() - 1); } private: TreeNode* helper(vectorint nums, int l, int r) { if (l r) { return nullptr; } int m (l r) / 2; TreeNode* root new TreeNode(nums[m]); root-left helper(nums, l, m - 1); root-right helper(nums, m 1, r); return root; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {number[]} nums * return {TreeNode} */ sortedArrayToBST(nums) { const helper (l, r) { if (l r) { return null; } const m Math.floor((l r) / 2); const root new TreeNode(nums[m]); root.left helper(l, m - 1); root.right helper(m 1, r); return root; }; return helper(0, nums.length - 1); } }/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public TreeNode SortedArrayToBST(int[] nums) { return Helper(nums, 0, nums.Length - 1); } private TreeNode Helper(int[] nums, int l, int r) { if (l r) { return null; } int m (l r) / 2; TreeNode root new TreeNode(nums[m]); root.left Helper(nums, l, m - 1); root.right Helper(nums, m 1, r); return root; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sortedArrayToBST(nums []int) *TreeNode { var helper func(l, r int) *TreeNode helper func(l, r int) *TreeNode { if l r { return nil } m : (l r) / 2 root : TreeNode{Val: nums[m]} root.Left helper(l, m-1) root.Right helper(m1, r) return root } return helper(0, len(nums)-1) }/** * Definition for a binary tree node. * class TreeNode(var val: Int 0) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { fun helper(l: Int, r: Int): TreeNode? { if (l r) { return null } val m (l r) / 2 val root TreeNode(nums[m]) root.left helper(l, m - 1) root.right helper(m 1, r) return root } return helper(0, nums.size - 1) } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func sortedArrayToBST(_ nums: [Int]) - TreeNode? { func helper(_ l: Int, _ r: Int) - TreeNode? { if l r { return nil } let m (l r) / 2 let root TreeNode(nums[m]) root.left helper(l, m - 1) root.right helper(m 1, r) return root } return helper(0, nums.count - 1) } }impl Solution { pub fn sorted_array_to_bst(nums: Veci32) - OptionRcRefCellTreeNode { fn helper(nums: [i32], l: i32, r: i32) - OptionRcRefCellTreeNode { if l r { return None; } let m (l r) / 2; let mut root TreeNode::new(nums[m as usize]); root.left helper(nums, l, m - 1); root.right helper(nums, m 1, r); Some(Rc::new(RefCell::new(root))) } helper(nums, 0, nums.len() as i32 - 1) } }复杂度分析时间复杂度$O(n)$每个元素恰好被访问一次创建 $n$ 个节点无复制开销空间复杂度递归调用栈 $O(\log n)$平衡树高度为 $\log n$输出树本身占用 $O(n)$仓库源码佐证索引边界版正是仓库中多数语言提交的实现。以 java/0108-convert-sorted-array-to-binary-search-tree.java 为例它把辅助函数命名为generateTree并采用了一个非常值得借鉴的细节——防溢出写法class Solution { public TreeNode sortedArrayToBST(int[] nums) { return generateTree(nums, 0, nums.length - 1); } public TreeNode generateTree(int[] nums, int low, int high) { if (low high) { return null; } int mid low ((high - low) / 2); TreeNode node new TreeNode(nums[mid]); node.left generateTree(nums, low, mid - 1); node.right generateTree(nums, mid 1, high); return node; } }注意第 11 行使用的是low ((high - low) / 2)而非(low high) / 2。当low high超过int上限时后者可能发生整数溢出而前者可以完全规避——这是生产代码中常见的防御性写法也是面试中容易加分的细节。c/0108-convert-sorted-array-to-binary-search-tree.c 采用了同样的边界递归思路并将辅助函数命名为dichomoty_rec二分递归同时用malloc手动分配节点内存struct TreeNode* dichomoty_rec(int* nums, int i, int j) { if (ij) return NULL; struct TreeNode* new_t malloc(sizeof(struct TreeNode)); int m (ij)/2; new_t-val nums[m]; new_t-left dichomoty_rec(nums, i, m-1); new_t-right dichomoty_rec(nums, m1, j); return new_t; } struct TreeNode* sortedArrayToBST(int* nums, int numsSize){ return dichomoty_rec(nums, 0, numsSize-1); }kotlin/0108-convert-sorted-array-to-binary-search-tree.kt 的实现还额外做了一层微优化当left right区间只剩一个元素时直接返回叶子节点省去一次多余的中间下标计算与递归展开class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { fun createTree(left: Int, right: Int): TreeNode? { if(left right) return null else if(left right) return TreeNode(nums[left]) val mid (left right) / 2 val node TreeNode(nums[mid]) node.left createTree(left, mid-1) node.right createTree(mid1, right) return node } return createTree(0, nums.lastIndex) } }解法三迭代 DFS显式栈直觉递归解法本质上依赖系统调用栈我们可以用显式栈将其改写成迭代形式。栈中存放待处理的工作项每个工作项包含一个待填充的节点以及它对应的数组边界。这样便模拟了递归调用栈的行为无需系统递归即可逐个子树处理从而彻底规避深递归可能导致的栈溢出风险。算法步骤若数组为空返回null。创建一个占位值的根节点。将根节点及其边界(0, n-1)压入栈。当栈非空时循环弹出包含节点及其边界(l, r)的工作项。计算中间下标将节点值设为nums[mid]。若左侧还有元素l mid - 1创建左孩子并入栈边界为(l, mid - 1)。若右侧还有元素mid 1 r创建右孩子并入栈边界为(mid 1, r)。返回根节点。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def sortedArrayToBST(self, nums: List[int]) - TreeNode: if not nums: return None root TreeNode(0) stack [(root, 0, len(nums) - 1)] while stack: node, l, r stack.pop() m (l r) // 2 node.val nums[m] if l m - 1: node.left TreeNode(0) stack.append((node.left, l, m - 1)) if m 1 r: node.right TreeNode(0) stack.append((node.right, m 1, r)) return root/** * 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; * } * } */ public class Solution { public TreeNode sortedArrayToBST(int[] nums) { if (nums.length 0) { return null; } TreeNode root new TreeNode(0); Stackint[] stack new Stack(); StackTreeNode nodes new Stack(); stack.push(new int[]{0, nums.length - 1}); nodes.push(root); while (!stack.isEmpty()) { int[] range stack.pop(); TreeNode node nodes.pop(); int l range[0], r range[1]; int m (l r) / 2; node.val nums[m]; if (l m - 1) { node.left new TreeNode(0); stack.push(new int[]{l, m - 1}); nodes.push(node.left); } if (m 1 r) { node.right new TreeNode(0); stack.push(new int[]{m 1, r}); nodes.push(node.right); } } return root; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { if (nums.empty()) return nullptr; TreeNode* root new TreeNode(0); stacktupleTreeNode*, int, int stack; stack.push({root, 0, (int)nums.size() - 1}); while (!stack.empty()) { auto [node, l, r] stack.top(); stack.pop(); int m (l r) / 2; node-val nums[m]; if (l m - 1) { node-left new TreeNode(0); stack.push({node-left, l, m - 1}); } if (m 1 r) { node-right new TreeNode(0); stack.push({node-right, m 1, r}); } } return root; } };/** * Definition for a binary tree node. * class TreeNode { * constructor(val 0, left null, right null) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { /** * param {number[]} nums * return {TreeNode} */ sortedArrayToBST(nums) { if (nums.length 0) { return null; } const root new TreeNode(0); const stack [[root, 0, nums.length - 1]]; while (stack.length) { const [node, l, r] stack.pop(); const m Math.floor((l r) / 2); node.val nums[m]; if (l m - 1) { node.left new TreeNode(0); stack.push([node.left, l, m - 1]); } if (m 1 r) { node.right new TreeNode(0); stack.push([node.right, m 1, r]); } } return root; } }/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val0, TreeNode leftnull, TreeNode rightnull) { * this.val val; * this.left left; * this.right right; * } * } */ public class Solution { public TreeNode SortedArrayToBST(int[] nums) { if (nums.Length 0) { return null; } TreeNode root new TreeNode(0); Stack(TreeNode, int, int) stack new Stack(TreeNode, int, int)(); stack.Push((root, 0, nums.Length - 1)); while (stack.Count 0) { var (node, l, r) stack.Pop(); int m (l r) / 2; node.val nums[m]; if (l m - 1) { node.left new TreeNode(0); stack.Push((node.left, l, m - 1)); } if (m 1 r) { node.right new TreeNode(0); stack.Push((node.right, m 1, r)); } } return root; } }/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func sortedArrayToBST(nums []int) *TreeNode { if len(nums) 0 { return nil } type item struct { node *TreeNode l, r int } root : TreeNode{Val: 0} stack : []item{{root, 0, len(nums) - 1}} for len(stack) 0 { curr : stack[len(stack)-1] stack stack[:len(stack)-1] m : (curr.l curr.r) / 2 curr.node.Val nums[m] if curr.l m-1 { curr.node.Left TreeNode{Val: 0} stack append(stack, item{curr.node.Left, curr.l, m - 1}) } if m1 curr.r { curr.node.Right TreeNode{Val: 0} stack append(stack, item{curr.node.Right, m 1, curr.r}) } } return root }/** * Definition for a binary tree node. * class TreeNode(var val: Int 0) { * var left: TreeNode? null * var right: TreeNode? null * } */ class Solution { fun sortedArrayToBST(nums: IntArray): TreeNode? { if (nums.isEmpty()) { return null } val root TreeNode(0) val stack ArrayDequeTripleTreeNode, Int, Int() stack.addLast(Triple(root, 0, nums.size - 1)) while (stack.isNotEmpty()) { val (node, l, r) stack.removeLast() val m (l r) / 2 node.val nums[m] if (l m - 1) { node.left TreeNode(0) stack.addLast(Triple(node.left!!, l, m - 1)) } if (m 1 r) { node.right TreeNode(0) stack.addLast(Triple(node.right!!, m 1, r)) } } return root } }/** * Definition for a binary tree node. * public class TreeNode { * public var val: Int * public var left: TreeNode? * public var right: TreeNode? * public init() { self.val 0; self.left nil; self.right nil; } * public init(_ val: Int) { self.val val; self.left nil; self.right nil; } * public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) { * self.val val * self.left left * self.right right * } * } */ class Solution { func sortedArrayToBST(_ nums: [Int]) - TreeNode? { if nums.isEmpty { return nil } let root TreeNode(0) var stack: [(TreeNode, Int, Int)] [(root, 0, nums.count - 1)] while !stack.isEmpty { let (node, l, r) stack.removeLast() let m (l r) / 2 node.val nums[m] if l m - 1 { node.left TreeNode(0) stack.append((node.left!, l, m - 1)) } if m 1 r { node.right TreeNode(0) stack.append((node.right!, m 1, r)) } } return root } }impl Solution { pub fn sorted_array_to_bst(nums: Veci32) - OptionRcRefCellTreeNode { if nums.is_empty() { return None; } let root Rc::new(RefCell::new(TreeNode::new(0))); let mut stack: Vec(RcRefCellTreeNode, usize, usize) vec![(Rc::clone(root), 0, nums.len() - 1)]; while let Some((node, l, r)) stack.pop() { let m (l r) / 2; node.borrow_mut().val nums[m]; if l m { let left Rc::new(RefCell::new(TreeNode::new(0))); node.borrow_mut().left Some(Rc::clone(left)); stack.push((left, l, m - 1)); } if m 1 r { let right Rc::new(RefCell::new(TreeNode::new(0))); node.borrow_mut().right Some(Rc::clone(right)); stack.push((right, m 1, r)); } } Some(root) } }复杂度分析时间复杂度$O(n)$每个元素仍只被处理一次空间复杂度显式栈最多同时存放 $O(\log n)$ 个工作项输出树本身占用 $O(n)$迭代版与前两种递归版在渐进复杂度上一致其价值在于不消耗系统调用栈。在数组规模极大递归深度达 $\log n$ 通常可控或运行环境栈空间受限的嵌入式/低资源场景下迭代 DFS 是更稳妥的选择。常见陷阱陷阱一子数组边界的 Off-by-One 错误递归构建子树时最常见的错误是把中间元素也包含进某一侧的子树导致无限递归或节点重复。# 错误 - 左子树错误地包含了 mid root.left helper(l, m) # 应该为 m - 1 # 正确 root.left helper(l, m - 1) root.right helper(m 1, r)判断标准很简单根节点已经取了nums[mid]那么左边界段必须是[l, mid-1]右边界段必须是[mid1, r]三者合起来恰好覆盖完整区间且互不重叠。对照三种解法可见切片版用nums[:mid]与nums[mid1:]天然排除了mid边界版用helper(l, m - 1)与helper(m 1, r)显式排除迭代版则用l m - 1与m 1 r两个条件守卫——它们遵守的是同一条不变式。陷阱二偶数长度数组的中间元素选择不一致对于长度为偶数的数组中间元素可以取(l r) // 2左中位也可以取(l r 1) // 2右中位。两种选择都能构造出合法的高度平衡 BST但若在同一份代码里混用会造成结果的不一致与调试困难。题目本身接受任意一种选择关键是始终如一地使用同一种约定。仓库中的 javascript/0108-convert-sorted-array-to-binary-search-tree.js 恰好给出了这个讨论的三种实证变体注释分别为DFS - Preorder | Left as mid、DFS - Preorder | Right as mid、DFS - Preorder | Random as mid左中位版const mid (left right) 1;与Math.floor((l r) / 2)等价右中位版当(left right)为奇数时mid 1即取(l r 1) // 2随机中位版奇数时mid Math.floor(Math.random() * 2)随机取左中位或右中位三者均标注Time O(N) | Space O(log(N))从实现层面印证了任选其一皆可、保持一致即可的结论。面试中推荐固定使用左中位(l r) // 2因为它与多数语言的默认整除语义一致最不易出错。三种解法对比与仓库实现一览解法核心思路时间复杂度空间复杂度适用场景解法一递归 数组切片每层复制子数组取中点为根$O(n \log n)$$O(n)$代码最直观适合快速演示分治思想输入规模小时无碍解法二递归 索引边界用(l, r)边界避免复制$O(n)$$O(\log n)$栈 $O(n)$输出面试/生产首选兼顾简洁与效率解法三迭代 显式栈用显式栈模拟递归$O(n)$$O(\log n)$栈 $O(n)$输出需要规避系统调用栈开销的场景本仓库为该题提供的多语言源码清单均可作为可运行、可验证的参考实现python/0108-convert-sorted-array-to-binary-search-tree.py解法一切片版go/0108-convert-sorted-array-to-binary-search-tree.go解法一切片版含空切片防御java/0108-convert-sorted-array-to-binary-search-tree.java解法二索引版含防溢出取中写法kotlin/0108-convert-sorted-array-to-binary-search-tree.kt解法二索引版含单元素早返回优化c/0108-convert-sorted-array-to-binary-search-tree.c解法二索引版C 语言malloc手动建树javascript/0108-convert-sorted-array-to-binary-search-tree.js解法二索引版附左中位/右中位/随机中位三种变体总结有序数组转高度平衡 BST是分治与递归思想的经典载体取中点为根、左右递归这一句话贯穿始终。掌握三条递进路径——朴素切片理解分治、索引边界消除复制开销、迭代栈摆脱系统递归配合对边界 off-by-one 与偶数长度取中约定的清醒认识就足以应对该题在任意面试变体中的考察。无论选择哪种解法最终产出的都是一棵中序遍历与升序数组严格对应、且高度为 $O(\log n)$ 的平衡 BST这正是有序数据在二叉搜索树中保持 $O(\log n)$ 查询性能的关键所在。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考