ac

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

class Rs{
    boolean isBalance;
    int height;

    public Rs(boolean isBalance, int height) {
        this.isBalance = isBalance;
        this.height = height;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long) Math.pow(2, 29);

    public static void main(String[] args) throws Exception {
        String line;
        String[] strArr;
        line = reader.readLine();
        strArr = line.split(" ");
        int n = Integer.valueOf(strArr[0]);
        int rootVal = Integer.valueOf(strArr[1]);
        Map<Integer, TreeNode> mp = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            line = reader.readLine();
            strArr = line.split(" ");
            int val = Integer.valueOf(strArr[0]);
            int leftVal = Integer.valueOf(strArr[1]);
            int rightVal = Integer.valueOf(strArr[2]);

            if (!mp.containsKey(val)) {
                mp.put(val, new TreeNode(val));
            }
            if (leftVal != 0) {
                if (!mp.containsKey(leftVal)) {
                    mp.put(leftVal, new TreeNode(leftVal));
                }
                mp.get(val).left = mp.get(leftVal);
            }
            if (rightVal != 0) {
                if (!mp.containsKey(rightVal)) {
                    mp.put(rightVal, new TreeNode(rightVal));
                }
                mp.get(val).right = mp.get(rightVal);
            }
        }
        TreeNode root = mp.get(rootVal);
        System.out.println(isSearchTree(root) ? "true": "false");
        System.out.println(isPrefectTree(root) ? "true": "false");
    }

    // 是否是二叉搜索树
    // 左 根 右
    static boolean isSearchTree(TreeNode root){
        if(root == null){
            return false;
        }
        boolean flag = true;
        int lastVal = 0;
        TreeNode cur = root;
        while (cur != null){
            if(cur.left == null){
                // 打印
                if(lastVal == 0){
                    lastVal = cur.val;
                }else {
                    if(cur.val <= lastVal) {
                        flag = false;
                    }
                    lastVal = cur.val;
                }
                cur = cur.right;
            }else {
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur){
                    pre = pre.right;
                }
                if(pre.right == null){ // 第一次访问
                    // 建立联系，并转向左节点
                    pre.right = cur;
                    cur = cur.left;
                }else { // 第二次访问,表示cur的左子树都访问过了
                    // 打印
                    if(lastVal == 0){
                        lastVal = cur.val;
                    }else {
                        if(cur.val <= lastVal) {
                            flag = false;
                        }
                        lastVal = cur.val;
                    }
                    pre.right = null;
                    cur = cur.right;
                }
            }
        }
        return flag;
    }

    // 是否是完全二叉树
    static boolean isPrefectTree(TreeNode root){
        if(root == null){
            return false;
        }
        boolean isLeafOccur = false;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()){
            TreeNode node = que.poll();
            if(!isLeafOccur && node.left == null && node.right == null){
                isLeafOccur = true;
            }
            // 已经出现了叶子节点了,但是接下来还是有非叶子节点，那么直接false
            if(isLeafOccur && (node.left != null || node.right != null)){
                return false;
            }
            // 完全二叉树不会出现左节点为null,而右节点不是null的情况
            if(node.left == null && node.right != null){
                return false;
            }
            if(node.left != null){
                que.offer(node.left);
            }
            if(node.right != null){
                que.offer(node.right);
            }else {
                isLeafOccur = true;
            }
        }
        return true;
    }

}
/*
49 47
47 30 21
30 14 11
14 26 3
26 16 37
16 36 7
36 0 0
7 0 0
37 1 27
1 0 0
27 0 0
3 8 39
8 48 33
48 0 0
33 0 0
39 19 44
19 0 0
44 0 0
11 40 35
40 13 15
13 29 6
29 0 0
6 0 0
15 42 5
42 0 0
5 0 0
35 31 25
31 41 38
41 0 0
38 0 0
25 17 18
17 0 0
18 0 0
21 45 4
45 34 2
34 22 46
22 20 49
20 0 0
49 0 0
46 0 0
2 10 28
10 0 0
28 0 0
4 23 24
23 12 9
12 0 0
9 0 0
24 32 43
32 0 0
43 0 0

false
true
 */