超出内存限制可能是因为递归的深度过大,导致栈空间不足。在你的代码中,当输入数组较大时,递归调用会很深,占用了大量的栈空间。
要解决这个问题,可以尝试使用迭代或优化递归算法。以下是一个使用迭代方法构建平衡二叉搜索树的示例代码:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}
stack := []*NodeInfo{{0, len(nums) - 1, nil}}
root := &TreeNode{}
for len(stack) > 0 {
nodeInfo := stack[len(stack)-1]
stack = stack[:len(stack)-1]
leftIdx, rightIdx, parent := nodeInfo.Left, nodeInfo.Right, nodeInfo.Parent
mid := (leftIdx + rightIdx) / 2
newNode := &TreeNode{Val: nums[mid]}
if parent != nil {
if mid < parent.Val {
parent.Left = newNode
} else {
parent.Right = newNode
}
} else {
root = newNode
}
if leftIdx < mid {
stack = append(stack, &NodeInfo{leftIdx, mid - 1, newNode})
}
if rightIdx > mid {
stack = append(stack, &NodeInfo{mid + 1, rightIdx, newNode})
}
}
return root
}
type NodeInfo struct {
Left, Right int
Parent *TreeNode
}
这个迭代的方法使用了一个辅助的数据结构 NodeInfo
,它存储了当前子数组的左右索引和父节点。通过不断迭代,将树的节点逐渐构建出来,避免了过深的递归调用。
使用这种迭代方法可以有效减少内存消耗,并解决超出内存限制的问题。
内容由零声教学AI助手提供,问题来源于学员提问