递归构建平衡二叉树算法栈溢出问题排查与修复

错误原因 #

你遇到的stack level too deep错误，核心问题确实是递归过程中反复修改self.root。每次调用build_balanced_tree都会重新创建并覆盖当前Tree实例的root属性，完全破坏了二叉树的层级结构，导致递归逻辑无法正确收敛，最终触发栈溢出。

修复方案 #

将「构建Tree根节点」和「递归构建子树」的逻辑分离：让递归函数只负责生成子树的Node实例，而Tree的root仅在首次调用时设置一次。

修正后的代码 #

class Node
  attr_accessor :value, :left, :right
  
  def initialize(value)
    @value = value
    @left = nil
    @right = nil
  end
end

class Tree
  attr_reader :array
  attr_accessor :root

  def initialize
    @array = nil
    @root = nil
  end

  def build_balanced_tree(array)
    return nil if array.empty?
    self.root = build_subtree(array)
  end

  private

  # 专门负责递归构建子树，仅返回Node实例，不修改Tree的root
  def build_subtree(array)
    return nil if array.empty?
    mid_index = (array.length - 1) / 2
    node = Node.new(array[mid_index])
    node.left = build_subtree(array[0...mid_index])
    node.right = build_subtree(array[(mid_index + 1)..-1])
    node
  end
end

array = [1, 4, 7, 13, 65, 97]
tree = Tree.new
tree.build_balanced_tree(array)
p tree.root

关键修复点 #

1. 新增私有方法build_subtree，专注于递归生成子树节点，每次返回一个独立的Node实例，避免修改Tree的全局root
2. 原build_balanced_tree仅负责调用子树构建方法，并设置一次Tree的root
3. 修正递归终止条件：空数组返回nil，让子节点的left/right正确设为nil
4. 简化数组切片写法：用array[0...mid_index]替代array[0..(mid_index-1)]，array[(mid_index+1)..-1]替代array[(mid_index+1)..(array.length-1)]，逻辑一致且更简洁

运行修正后的代码，会正确生成以7为根的平衡二叉树，左子树以4为根、右子树以65为根，不再出现栈溢出问题。

内容的提问来源于stack exchange，提问作者jbk