演習課題「二分探索木の判定」
二分木について、頂点の数 N と根に紐づく値 R、N-1 個の辺について両端の頂点に紐づく値と子の位置の組(親: a_i, 子: b_i, 子の位置: LR_i)が与えられるので、この二分木が二分探索木であるか判定して結果を出力してください。
コードエリアには、入力値を受け取るコードと、判定結果を出力するコードが実装されているので、コードを書き足して完成させてください。
制約
・入力はすべて整数
・1 ≦ N ≦ 100
・1 ≦ R ≦ N
・1 ≦ a_i , b_i ≦ N (1 ≦ i ≦ N-1)
・LR_i は 'L' または 'R'(1 ≦ i ≦ N-1)
・与えられる二分木の高さは 20 未満である
・a_i は「根の頂点の値」または「親の頂点が確定している頂点の値」である
・与えられる二分木の中に同じ値は 2 つ以上含まれない
期待する出力値
NO
＃07:二分探索木の判定
このチャプターでは、二分探索木の判定について学習します。
レベルアップ問題集「木のメニュー」に収録されている「二分探索木の判定」の問題を解きます。
次の条件を両方満たす二分木
・親の頂点に紐づく値が左の子とその子孫に紐づく値以上
・親の頂点に紐づく値が右の子とその子孫に紐づく値以下
頂点の子は左右を区別
・親の頂点に紐づく値の大小関係によって頂点の左右が決まる
・大小関係のある値の集合を効率よく操作
入力
・木の頂点の数N, 根に紐づく値R
・N-1個の辺 (a_1, b_1, LR_1), (a_2, b_2, LR_2), ..., (a_{N-1}, b_{N-1}, LR_{N-1})
出力
・木が二分探索木であるならば"YES", そうでなければ"NO"
【今回の問題の詳細】
・二分木であるかはチェックしなくてよい
・直接の親子の大小関係のみのチェックでよい
【頂点に紐づく値】
・今回の問題では頂点ごとに異なる
・頂点を識別するために利用できる
【今回の実装】
weight：頂点に紐づく値
id：頂点を表す値
3 2
2 3 L
2 1 R
NO
5 6
6 3 L
6 8 R
3 1 L
3 5 R
YES
import java.util.*;
public class Main {
static Map<Integer, Integer> weightAndId = new HashMap<>();
static Map<Integer, Integer> idAndWeight = new HashMap<>();
// 頂点のweightに対応する頂点のidを取得する
static int getIdFromWeight(int weight) {
if (!weightAndId.containsKey(weight)) { // 新しいweightならば、新しいidを割り振る
weightAndId.put(weight, weightAndId.size());
}
int id = weightAndId.get(weight);
idAndWeight.put(id, weight);
return id;
}
// 頂点のidに対応するweightを取得する
static int getWeight(int id) {
return idAndWeight.get(id);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 頂点の数
int R = sc.nextInt(); // 根の頂点のweight
int[] tree = new int[N]; // 根付き木に対応する配列
char[] lrChild = new char[N]; // 左右いずれの子かを表す配列
// 各頂点の親を自身として初期化
for (int i = 0; i < N; i++) {
tree[i] = i;
}
// 辺の数だけループして入力
for (int i = 0; i < N-1; i++) {
int aw = sc.nextInt();
int bw = sc.nextInt();
char lr = sc.next().charAt(0);
int aid = getIdFromWeight(aw);
int bid = getIdFromWeight(bw);
// 頂点bの親を頂点aとする
tree[bid] = aid;
// 頂点bが左右のどちらの子かを保存する
lrChild[bid] = lr;
}
// 二分探索木の判定
boolean isBinarySearchTree = true;
for (int i = 0; i < N; i++) {
int childId = i;
int parentId = tree[i];
int lr = lrChild[i];
// 根ならば何もしない
if (childId == parentId) {
continue;
}
if (lr == 'L') {
// 左の子の頂点ならば (親の頂点のweight) >= (左の子の頂点のweight)
if (getWeight(parentId) < getWeight(childId)) {
isBinarySearchTree = false;
}
} else if (lr == 'R') {
// 右の子の頂点ならば (親の頂点のweight) <= (右の子の頂点のweight)
if (getWeight(parentId) > getWeight(childId)) {
isBinarySearchTree = false;
}
}
}
if (isBinarySearchTree) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}