ruby - 查找二叉树的最深节点

Question

我有一个高度方法可以找到二叉树的高度，但不确定如何返回二叉树的最深节点(如果深度相同则返回多个节点)。

BinaryNode.new(1,BinaryNode.new(2,leaf,leaf),BinaryNode.new(3,leaf,leaf))

其中叶子代表空

这棵树的高度是2，最深的节点是2,3(相同深度)

class BinaryNode 
  include Enumerable
  def initialize(element,lchild,rchild)
    @element, @lchild, @rchild = element, lchild, rchild
  end
  def deepestNode
    if self.nil?
      0
    else
      height1=@lchild.height+1
      height2=@lchild.height+1
    end
      height=[height1,height2].max
      height
    end
  end
end

Answer 1

假设:

• 二叉树其实就是根节点
• child_nodes 以数组的形式返回子节点的集合

---

class BinaryNode
  attr_reader :element

  def initialize(element,lchild,rchild)
    @element, @lchild, @rchild = element, lchild, rchild
  end

  def height
    if @lchild.nil? && @rchild.nil?
      return 0
    else
     [@lchild, @rchild].collect {|n| n.nil ? 0 : n.height + 1 }.max      
    end
  end

  def deepest_nodes
    return [self] if self.height == 1

    [@lchild, @rchild].select {|n| !n.nil? && (n.height == self.height - 1)}.collect {|n| n.deepest_nodes}.flatten
  end
end

---

重构:

class BinaryNode
  attr_reader :element

  def initialize(element,lchild,rchild)
    @element, @lchild, @rchild = element, lchild, rchild
  end

  def child_nodes
    [@lchild, @rchild].compact
  end

  def height
    if self.child_nodes.empty?
      return 0
    else
      self.child_nodes.collect {|n| n.height + 1 }.max      
    end
  end

  def deepest_nodes
    return [self] if self.depth == 1

    self.child_nodes.select {|n| n.height == self.height - 1}.collect {|n| n.deepest_nodes}.flatten
  end
end

---

获取元素:

BinaryNode.new(1,BinaryNode.new(2,leaf,leaf),BinaryNode.new(3,leaf,leaf)).deepest_nodes.collect {|n| n.element }