题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        HashMap<Integer, Node> hm = new HashMap<>();
        Node head = new Node(sc.nextInt());
        hm.put(head.value, head);
        int f, l, r;
        Node fNode;
        for(int i = 0; i < len; i++) {
            fNode = hm.get(sc.nextInt());
            l = sc.nextInt();
            r = sc.nextInt();
            if(l != 0) {
                fNode.left = new Node(l);
                hm.put(l, fNode.left);
            }
            if(r != 0) {
                fNode.right = new Node(r);
                hm.put(r, fNode.right);
            }
        }
        Boolean isBST = isBSTPro(head);
        Boolean isBCT = isBCTPro(head);
        System.out.println(isBST);
        System.out.println(isBCT);
    }
    
    public static Boolean isBSTPro(Node head) {
        if(head == null) return true;
         // morris中序遍历，当遍历到前一个大于后一个的时候，return false;
        Node cur = head;
        Node pre = null;
        Node mRight = null;
        Boolean res = true;
        while(cur != null) {
            mRight = cur.left;
            if(mRight != null) {
                while(mRight.right != null && mRight.right != cur) {
                    mRight = mRight.right;
                }
                if(mRight.right == null) {
                    mRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mRight.right = null;
                }
            }
            if(pre != null && pre.value > cur.value) {
                res = false;
              // 注意：morris遍历不能直接return false结束，否则改变了原有的树结构！！！
            }
            pre = cur;
            cur = cur.right;
        }
        return res;
    }
    public static Boolean isBCTPro(Node head) {
        if(head == null) return true;
        // 按层遍历这棵树
        // 使用isLeaf标记上一个遍历的节点是否是叶子节点
        
        // return false的几种情况。
        // 1. 左孩子没有，右孩子在。
        // 2. 有左孩子或者右孩子，但是isLeaf为true。三种情况：1. 左有右空。2. 左空右空。3. 左空右有。
        Node cur = head;
        Queue<Node> q = new LinkedList<>();
        q.offer(head);
        Boolean isLeaf = false;
        while(!q.isEmpty()) {
            cur = q.poll();
            // 操作cur
            if(cur.left == null && cur.right != null) {
                return false;
            }
            if((cur.left != null || cur.right != null) && isLeaf) {
                return false;
            }
            if(cur.left != null) {
                q.offer(cur.left);
            }
            if(cur.right != null) {
                q.offer(cur.right);
            } else {
                isLeaf = true;
            }
        }
        return true;
    }
}
class Node {
    Node left;
    Node right;
    int value;
    public Node(int value) {
        this.value = value;
    }
}