solution.java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class _09BST插入节点问题 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] parent = new int[n];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            parent[i] = sc.nextInt();
            map.put(i + 1, sc.nextInt());
        }
        ArrayList<Integer> childs = new ArrayList<Integer>();
        int rootWeight = map.get(1);
        int kWeight = map.get(k);
        for (int i = 0; i < parent.length; i++) {
            if (k == parent[i])
                childs.add(map.get(i + 1));
        }
        // 1.parents不存在的节点就是叶子节点，叶子节点的答案是无穷大
        if (childs.size() == 0) {
            System.out.println("叶子节点");
            System.out.println(-1);
            return;
        }
        // 2. 已经有左右孩子，答案是0
        else if (childs.size() == 2) {
            System.out.println("已经有左右孩子了");
            System.out.println(0);
            return;
        }
        // 3. 在右子树：k节点有左无右时为-1; 在左子树：k几点有右无左为-1
        else if (childs.size() == 1 && (kWeight > rootWeight && childs.get(0) < kWeight)
                || (kWeight < rootWeight && childs.get(0) > kWeight)) {
            System.out.println(-1);
            return;
        } else {
            int fatherWeight = map.get(parent[k - 1]);
            System.out.println(Math.abs(kWeight - fatherWeight) - 1);
            return;
        }
    }

}