新・アルゴリズムとデータ構造入門 Java編13:二分木の性質を利用した二分探索木の判定

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 頂点の数
        int R = sc.nextInt(); // 根の頂点のweight

        // 辺の数だけループして入力
        for (int i = 0; i < N-1; i++) {
            int aw = sc.nextInt();
            int bw = sc.nextInt();
            char lr = sc.next().charAt(0);

        }
    }
}

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 頂点の数
        int R = sc.nextInt(); // 根の頂点のweight

        // 辺の数だけループして入力
        for (int i = 0; i < N-1; i++) {
            int aw = sc.nextInt();
            int bw = sc.nextInt();
            char lr = sc.next().charAt(0);

        }
    }
}

import java.util.*;

public class Main {
    final static int MAX_BINARY_TREE_SIZE = 1 << 20;

    static Map<Integer, Integer> weightAndId = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int R = sc.nextInt();
        int[] binaryTree = new int[MAX_BINARY_TREE_SIZE];

        for (int i = 0; i < MAX_BINARY_TREE_SIZE; i++) {
            binaryTree[i] = -1;
        }

        binaryTree[0] = R;
        weightAndId.put(R, 0);

        for (int i = 0; i < N-1; i++) {
            int aw = sc.nextInt();
            int bw = sc.nextInt();
            char lr = sc.next().charAt(0);

            int aid = weightAndId.get(aw);
            int bid = -1;
            if (lr == 'L') {
                bid = /* */;
            } else {
                bid = /* */;
            }

            binaryTree[bid] = bw;
            weightAndId.put(bw, bid);
        }

        boolean isBinarySearchTree = true;
        for (int i = 1; i < MAX_BINARY_TREE_SIZE; i++) {
            int childId = i;
            int parentId = (childId - 1) / 2;

            if (binaryTree[childId] == -1) {
                continue;
            }

            if (/* */ == childId) {
                if (/* */) {
                    isBinarySearchTree = false;
                }
            } else if (/* */ == childId) {
                if (/* */) {
                    isBinarySearchTree = false;
                }
            }
        }

        if (isBinarySearchTree) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

import java.util.*;

public class Main {
    final static int MAX_BINARY_TREE_SIZE = 1 << 20;

    static Map<Integer, Integer> weightAndId = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int R = sc.nextInt();
        int[] binaryTree = new int[MAX_BINARY_TREE_SIZE];

        for (int i = 0; i < MAX_BINARY_TREE_SIZE; i++) {
            binaryTree[i] = -1;
        }

        binaryTree[0] = R;
        weightAndId.put(R, 0);

        for (int i = 0; i < N-1; i++) {
            int aw = sc.nextInt();
            int bw = sc.nextInt();
            char lr = sc.next().charAt(0);

            int aid = weightAndId.get(aw);
            int bid = -1;
            if (lr == 'L') {
                bid = /* */;
            } else {
                bid = /* */;
            }

            binaryTree[bid] = bw;
            weightAndId.put(bw, bid);
        }

        boolean isBinarySearchTree = true;
        for (int i = 1; i < MAX_BINARY_TREE_SIZE; i++) {
            int childId = i;
            int parentId = (childId - 1) / 2;

            if (binaryTree[childId] == -1) {
                continue;
            }

            if (/* */ == childId) {
                if (/* */) {
                    isBinarySearchTree = false;
                }
            } else if (/* */ == childId) {
                if (/* */) {
                    isBinarySearchTree = false;
                }
            }
        }

        if (isBinarySearchTree) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

この動画を見るには

paiza会員登録のうえ

有料会員登録が必要です

演習1

問題ログインすると模範解答や入力を見ることができます

演習課題「二分木の性質を利用した二分探索木の判定」

二分木について、頂点の数 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 つ以上含まれない

入力される値

3 2
2 3 L
2 1 R

標準入力からの値取得方法はこちらをご確認ください

期待する出力値

Tips

動画へ戻る

次のレッスンへ前のチャプターへ

※有料会員になるとこの動画をご利用いただけます

詳しい説明を読む

＃08:二分木の性質を利用した二分探索木の判定

このチャプターでは、二分木の性質を利用した二分探索木の判定について学習します。
レベルアップ問題集「木のメニュー」に収録されている「二分探索木の判定」の問題を解きます。

3 2
2 3 L
2 1 R

出力例1

NO

入力例2

出力例2

YES

完成コード

import java.util.*;

public class Main {
    final static int MAX_BINARY_TREE_SIZE = 1 << 20; // 高さ20までの二分木を扱う

    static Map<Integer, Integer> weightAndId = new HashMap<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 頂点の数
        int R = sc.nextInt(); // 根の頂点のweight
        int[] binaryTree = new int[MAX_BINARY_TREE_SIZE]; // 二分木に対応する配列

        // 存在しない頂点のweightは-1
        for (int i=0; i<MAX_BINARY_TREE_SIZE; i++) {
            binaryTree[i] = -1;
        }

        // 根のidとweightを紐づける
        binaryTree[0] = R;
        weightAndId.put(R, 0);

        // 辺の数だけループして入力
        for (int i = 0; i < N-1; i++) {
            int aw = sc.nextInt();
            int bw = sc.nextInt();
            char lr = sc.next().charAt(0);

            // 親の頂点のidから子の頂点のidを計算する
            int aid = weightAndId.get(aw);
            int bid = -1;
            if (lr == 'L') {
                bid = aid * 2 + 1;
            } else {
                bid = aid * 2 + 2;
            }

            // idとweightを紐づける
            binaryTree[bid] = bw;
            weightAndId.put(bw, bid);
        }

        // 二分探索木の判定
        boolean isBinarySearchTree = true;
        for (int i = 1; i < MAX_BINARY_TREE_SIZE; i++) {
            int childId = i;
            int parentId = (childId - 1) / 2; // 子の頂点のidから親の頂点のidを求める

            // 頂点が存在しないならばスキップ
            if (binaryTree[childId] == -1) {
                continue;
            }

            if (parentId * 2 + 1 == childId) {
                // 左の子の頂点ならば (親の頂点のweight) >= (左の子の頂点のweight)
                if (binaryTree[parentId] < binaryTree[childId]) {
                    isBinarySearchTree = false;
                }
            } else if (parentId * 2 + 2 == childId) {
                // 右の子の頂点ならば (親の頂点のweight) <= (右の子の頂点のweight)
                if (binaryTree[parentId] > binaryTree[childId]) {
                    isBinarySearchTree = false;
                }
            }
        }

        if (isBinarySearchTree) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}