目前导致溢出的递归树构建算法有什么问题？

Question

我正在学习二叉树，并尝试编写一种递归方法，在给定排序数组时构建平衡二叉树。我陷入了溢出状态，并没有确切地看到我做错了什么以及如何解决。一些指导会很有帮助。有问题的方法是

#build_balanced_tree(array)

，生成可重现示例的所有相关代码如下：

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 if array.empty?
    array_mid_index = (array.length - 1) / 2
    self.root = Node.new(array[array_mid_index])
    self.root.left = build_balanced_tree(array[0..(array_mid_index - 1)])
    self.root.right = build_balanced_tree(array[(array_mid_index + 1)..(array.length - 1)])
    return root
  end
end

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

这个错误信息；

:in 'new': stack level too deep (SystemStackError)

当代码命中

self.root.left = ...

行并将数组的左半部分传回自身时抛出。

我怀疑部分问题可能是我的递归方法正在设置

self.root

并且因为

@root

被显式命名，所以它递归地不断覆盖自己，但我无法完全想象如何匿名化

Node

创建和值设置同时确保在第一次迭代时设置

@root

。此代码也可能存在多个其他问题，我将不胜感激。谢谢。

Answer 1

无限递归的原因是

array[0..(array_mid_index - 1)]

可以变成

array[0..-1]

，这意味着whole数组，而当array_mid_index为0时你真的想得到一个

empty

数组。

有几种方法可以解决这个问题；一种是使用

slice

，它将长度作为第二个参数，因此可以是

array_mid_index

。那么就不可能有这样的误解。

你也是对的，分配给

self.root

有问题。您只希望该赋值发生一次，这意味着您不应在将递归调用的函数中执行该赋值，而应在单独的函数中执行。

我建议为此目的创建一个 static 方法，因为调用者在实际调用此函数之前必须创建一个新的 Tree 实例感觉不自然。静态方法可以自己创建新实例并在填充后返回它。

递归函数可以成为

Node

类的静态方法，因为它不需要

Tree

类的任何知识。

NB：您不需要

@array

类上的

Tree

属性。数组只是一个参数，临时用于构建树，然后在树的状态中没有任何作用。

这是它的样子：

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

  def self.build_balanced_tree(array)
    return if array.empty?
    array_mid_index = (array.length - 1) / 2
    node = Node.new(array[array_mid_index])
    node.left = build_balanced_tree(array.slice(0, array_mid_index))
    node.right = build_balanced_tree(array[(array_mid_index + 1)...])
    return node
  end
end

class Tree
  attr_accessor :root

  def initialize
    @root = nil
  end

  def self.build_balanced_tree(array)
    tree = Tree.new
    tree.root = Node.build_balanced_tree(array)
    return tree
  end
end

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