给定一棵二叉树,已经其中没有重复值的节点,请判断该二叉树是否为搜索二叉树和完全二叉树。
import java.util.Scanner;
public class Main {
private static CBTInfo solveCBT(Node root) {
if (root == null) {
return new CBTInfo(0, true, true);
}
CBTInfo leftInfo = solveCBT(root.left);
CBTInfo rightInfo = solveCBT(root.right);
if (leftInfo.height == rightInfo.height) {
return new CBTInfo(leftInfo.height + 1, leftInfo.isFull && rightInfo.isFull,
leftInfo.isFull && rightInfo.isCBT);
} else {
if (leftInfo.height == rightInfo.height + 1) {
return new CBTInfo(leftInfo.height + 1, false,
leftInfo.isCBT && rightInfo.isFull);
} else {
return new CBTInfo(rightInfo.height + 1, false, false);
}
}
}
private static BSTInfo solveBST(Node root) {
if (root == null) {
return new BSTInfo(true, null, null);
}
BSTInfo leftInfo = solveBST(root.left);
BSTInfo rightInfo = solveBST(root.right);
if (leftInfo.isBST && (leftInfo.mostRight == null || leftInfo.mostRight.val < root.val) &&
rightInfo.isBST && (rightInfo.mostLeft == null || rightInfo.mostLeft.val > root.val)) {
return new BSTInfo(true, leftInfo.mostRight == null ? root : leftInfo.mostRight,
rightInfo.mostRight == null ? root : rightInfo.mostRight);
}
return new BSTInfo(false, leftInfo.mostRight == null ? root : leftInfo.mostRight,
rightInfo.mostRight == null ? root : rightInfo.mostRight);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
Node[] nodes = new Node[n + 1];
for (int i = 1; i <= n; ++i) {
nodes[i] = new Node(i);
}
Node root = nodes[in.nextInt()];
for (int i = 1; i <= n; ++i) {
int fa = in.nextInt();
nodes[fa].left = nodes[in.nextInt()];
nodes[fa].right = nodes[in.nextInt()];
}
BSTInfo bstInfo = solveBST(root);
CBTInfo cbtInfo = solveCBT(root);
System.out.println(bstInfo.isBST);
System.out.println(cbtInfo.isCBT);
}
}
}
class Node {
Node left;
Node right;
int val;
public Node(int val) {
this.val = val;
}
}
class CBTInfo {
int height;
boolean isFull;
boolean isCBT;
public CBTInfo(int height, boolean isFull, boolean isCBT) {
this.height = height;
this.isFull = isFull;
this.isCBT = isCBT;
}
}
class BSTInfo {
boolean isBST;
Node mostLeft;
Node mostRight;
public BSTInfo(boolean isBST, Node mostLeft, Node mostRight) {
this.isBST = isBST;
this.mostLeft = mostLeft;
this.mostRight = mostRight;
}
}