B木の共通の祖先で最短のものを表示。
いきなり難易度が上がった感じ。これ苦手だわ。
とりあえずB木をどう表現するかが肝っぽい。
設問
Write a program to determine the lowest common ancestor of two nodes in a binary search tree. You may hardcode the following binary search tree in your program:
30 | ____ | | 8 52 | ____ | | 3 20 | ____ | | 10 29
Input sample:
The first argument will be a text file containing 2 values that represent two nodes within the tree, one per line. e.g.
8 52 3 29
Output sample:
Print to stdout, the least common ancestor, one per line.
e.g.
30 8
やってみた
#!/usr/bin/env ruby class Node attr_accessor :value, :left, :right def initialize(value=nil) @value = value @left, @right = nil, nil end def ancestor(n) return value if (left and n == left.value) or (right and n == right.value) left.ancestor(n).instance_eval{ |v| return v if v } if left right.ancestor(n).instance_eval{ |v| return v if v } if right end def ancestors(n, arr=[]) anc = ancestor(n) return arr unless anc arr << anc ancestors(anc, arr) end end tree = Node.new(30) tree.left = Node.new(8) tree.left.left = Node.new(3) tree.left.right = Node.new(20) tree.left.right.left = Node.new(10) tree.left.right.right = Node.new(29) tree.right = Node.new(52) ARGF.lines do |line| a, b = line.split(/\s/).map(&:to_i) puts (tree.ancestors(a) & tree.ancestors(b)).first end
どうもtreeデータの作成が汚いなぁ。
あと、ancestor取得のところもleft/rightで一緒なのでなんとかならんかな。