二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）

给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式：

输入在第一行给出一个正整数N（≤100），随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（≤100），随后M行，每行给出一句待判断的陈述句。陈述句有以下6种：

• A is the root，即"A是树的根"；
• A and B are siblings，即"A和B是兄弟结点"；
• A is the parent of B，即"A是B的双亲结点"；
• A is the left child of B，即"A是B的左孩子"；
• A is the right child of B，即"A是B的右孩子"；
• A and B are on the same level，即"A和B在同一层上"。

题目保证所有给定的整数都在整型范围内。

输出格式：

对每句陈述，如果正确则输出Yes，否则输出No，每句占一行。

输入样例：

5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3

输出样例：

Yes
Yes
Yes
Yes
Yes
No
No
No

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

Java实现：

/**
 * 逻辑大概是这样的：
 * 1. 搞个树：按照题目给的顺序一个一个往里塞，做成标准的二叉搜索树。塞的时候顺便记下每个人的父节点是谁，在哪一层。
 * 2. 存个表：用个 HashMap 把值和节点对应起来，这样待会儿查某个数字的信息，直接搜一下就行，不用满树跑。
 * 3. 读句子：句子虽然长，但关键点就那么几个词。看句子里有没有 "root"、"parent" 之类的关键词，
 * 顺便把句子里的数字抠出来。
 * 4. 给答案：拿到数字去表里查，看看是不是 root，或者是不是同一个父节点，位置对不对，最后回个 Yes 或 No。
 */

import java.util.*;
import java.io.*;

public class Main {
    // 节点类，存值、父节点、左右孩子和深度
    static class Node {
        int val, depth;
        Node left, right, parent;
        Node(int val, int depth, Node parent) {
            this.val = val;
            this.depth = depth;
            this.parent = parent;
        }
    }

    // map 用来快速定位节点，不用每次都去遍历树
    static Map<Integer, Node> map = new HashMap<>();
    static Node root = null;

    public static void main(String[] args) throws IOException {
        FastReader fr = new FastReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        // 1. 读入 N 个数开始搭树
        int N = fr.nextInt();
        for (int i = 0; i < N; i++) {
            root = insert(root, fr.nextInt(), 0, null);
        }

        // 2. 读入 M 个查询
        int M = fr.nextInt();
        for (int i = 0; i < M; i++) {
            String line = fr.nextLine();
            // 判断 solve 给的结果，Yes 或者 No
            if (line != null && solve(line)) out.println("Yes");
            else out.println("No");
        }
        out.flush();
        out.close();
    }

    // 标准的 BST 插入，小的往左走，大的往右走
    static Node insert(Node node, int val, int depth, Node parent) {
        if (node == null) {
            Node newNode = new Node(val, depth, parent);
            map.put(val, newNode); // 塞进 map 方便待会儿搜
            return newNode;
        }
        if (val < node.val) node.left = insert(node.left, val, depth + 1, node);
        else node.right = insert(node.right, val, depth + 1, node);
        return node;
    }

    

    // 解析句子的逻辑
    static boolean solve(String line) {
        String[] words = line.split(" ");
        try {
            // A 是不是根节点
            if (line.endsWith("root")) {
                int a = Integer.parseInt(words[0]);
                return map.containsKey(a) && map.get(a) == root;
            } 
            
            // A 和 B 是不是亲兄弟（同一个父亲）
            if (line.contains("siblings")) {
                int a = Integer.parseInt(words[0]);
                int b = Integer.parseInt(words[2]);
                if (!map.containsKey(a) || !map.containsKey(b)) return false;
                Node na = map.get(a), nb = map.get(b);
                return na.parent != null && nb.parent != null && na.parent == nb.parent;
            } 
            
            // A 是不是 B 的父亲
            if (line.contains("parent")) {
                int a = Integer.parseInt(words[0]); 
                int b = Integer.parseInt(words[words.length - 1]);
                if (!map.containsKey(a) || !map.containsKey(b)) return false;
                return map.get(b).parent == map.get(a);
            } 
            
            // A 是不是 B 的左儿子
            if (line.contains("left child")) {
                int a = Integer.parseInt(words[0]); 
                int b = Integer.parseInt(words[words.length - 1]);
                if (!map.containsKey(a) || !map.containsKey(b)) return false;
                return map.get(b).left == map.get(a);
            } 
            
            // A 是不是 B 的右儿子
            if (line.contains("right child")) {
                int a = Integer.parseInt(words[0]); 
                int b = Integer.parseInt(words[words.length - 1]);
                if (!map.containsKey(a) || !map.containsKey(b)) return false;
                return map.get(b).right == map.get(a);
            } 
            
            // A 和 B 是不是在同一层（深度一样）
            if (line.contains("same level")) {
                int a = Integer.parseInt(words[0]);
                int b = Integer.parseInt(words[2]);
                if (!map.containsKey(a) || !map.containsKey(b)) return false;
                return map.get(a).depth == map.get(b).depth;
            }
        } catch (Exception e) {
            return false;
        }
        return false;
    }

    // 这一堆是用来加速读数据的，比普通的快不少
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    String s = br.readLine();
                    if (s == null) return null;
                    st = new StringTokenizer(s);
                } catch (IOException e) {
                    return null;
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (IOException e) {
                return null;
            }
        }
    }
}