boom.rb

# @param {Integer} n
# @return {TreeNode[]}
def generate_trees(n, vals = (1..n).to_a)
  return [] if vals.empty?
  return [TreeNode.new(vals.first)] if (vals.length == 1)

  nodes = Array.new
  all_rights = generate_trees(n, vals[1...vals.length])
  all_rights.each { |right|
    node = TreeNode.new(vals.first)
    node.right = right
    nodes.push(node)
  }
  all_lefts = generate_trees(n, vals[0...vals.length-1])
  all_lefts.each { |left|
    node = TreeNode.new(vals.last)
    node.left = left
    nodes.push(node)
  }

  1.upto(vals.length-2) { |index|
    lefts = generate_trees(n, vals[0...index])
    rights = generate_trees(n, vals[index+1...vals.length])
    lefts.each { |left|
      rights.each { |right|
        node = TreeNode.new(vals[index])
        node.left = left
        node.right = right
        nodes.push(node)
      }
    }
  }
  return nodes
end