1. 判断二叉树是完全二叉树
完全二叉树，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
class Info5 {
public int height;
public boolean full;
public boolean cbt;
public Info5(int height, boolean full, boolean cbt) {
this.height = height;
this.full = full;
this.cbt = cbt;
}
}
public Info5 processCBT(BiNode node) {
if (node == null) {
return new Info5(0, true, true);
}
Info5 left = processCBT(node.left);
Info5 right = processCBT(node.right);
int height = Math.max(left.height, right.height) + 1;
boolean full = left.full && right.full && left.height == right.height;
boolean cbt = full
|| (left.cbt && right.full && left.height - right.height == 1)
|| (left.full && right.full && left.height - right.height == 1)
|| (left.full && right.cbt && left.height == right.height);
return new Info5(height, full, cbt);
}
public boolean isCompleteTreeCompare(BiNode node) {
return processCBT(node).cbt;
}
public boolean isCompleteTree(BiNode node) {
if (node == null) {
return true;
}
Queue<BiNode> queue = new LinkedList<>();
queue.add(node);
BiNode l, r;
BiNode node1;
boolean isLeaf = false;
while (!queue.isEmpty()) {
node1 = queue.poll();
l = node1.left;
r = node1.right;
if (isLeaf && (l != null || r != null)) {
return false;
}
if (l == null && r != null) {
return false;
}
if (l != null) {
queue.add(l);
}
if (r != null) {
queue.add(r);
}
isLeaf = !(l != null && r != null);
}
return true;
}
@Test
public void test1() {
for (int i = 0; i < 10000; i++) {
BiNode node = Reduce.binaryTree(5, 100);
boolean r1 = isCompleteTree(node);
boolean r2 = isCompleteTreeCompare(node);
if (r1 != r2) {
System.out.println(Printer.print(node));
System.out.println(r1);
System.out.println(r2);
return;
}
}
}
2. 头节点是 head， 求任一两个节点 a, b 的最低公共父节点
class Info7 {
public boolean findA;
public boolean findB;
public BiNode node;
public Info7(boolean findA, boolean findB, BiNode node) {
this.findA = findA;
this.findB = findB;
this.node = node;
}
}
public BiNode lowParent(BiNode head, BiNode a, BiNode b) {
return processLowPrt(head, a, b).node;
}
private Info7 processLowPrt(BiNode head, BiNode a, BiNode b) {
if (head == null) {
return new Info7(false, false, null);
}
Info7 left = processLowPrt(head.left, a, b);
Info7 right = processLowPrt(head.right, a, b);
boolean findA = left.findA || right.findA || head == a,
findB = left.findB || right.findB || head == b;
BiNode node = left.node != null ? left.node : right.node != null ? right.node : findA && findB ? head : null;
return new Info7(findA, findB, node);
}
public BiNode lowParentCompare(BiNode node, BiNode a, BiNode b) {
if (node == null || a == null || b == null) {
return null;
}
Map<BiNode, BiNode> node2parent = new HashMap<>();
Stack<BiNode> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
BiNode n = stack.pop();
if (n.right != null) {
node2parent.put(n.right, n);
stack.push(n.right);
}
if (n.left != null) {
node2parent.put(n.left, n);
stack.push(n.left);
}
}
Set<BiNode> set = new HashSet<>();
while (a != null) {
set.add(a);
a = node2parent.get(a);
}
while (b != null) {
if (!set.add(b)) {
return b;
}
b = node2parent.get(b);
}
return null;
}
@Test
public void test3() {
for (int i = 0; i < 10000; i++) {
BiNode node = Reduce.binaryTree(10, 100);
List<BiNode> nodes = Reduce.elements(node);
BiNode a = null, b = null;
if (nodes.size() > 0) {
a = nodes.get(Reduce.num(0, nodes.size() - 1));
b = nodes.get(Reduce.num(0, nodes.size() - 1));
}
BiNode r1 = lowParent(node, a, b);
BiNode r2 = lowParentCompare(node, a, b);
if (r1 != r2) {
System.out.println(Printer.print(node));
System.out.println(r1);
System.out.println(r2);
return;
}
}
}
3. 判断是否是满二叉树
class Info6 {
public int height;
public boolean full;
public Info6(int height, boolean full) {
this.height = height;
this.full = full;
}
}
public boolean isFull(BiNode node) {
return processFull(node).full;
}
private Info6 processFull(BiNode node) {
if (node == null) {
return new Info6(0, true);
}
Info6 left = processFull(node.left);
Info6 right = processFull(node.right);
return new Info6(
Math.max(left.height, right.height) + 1,
left.full && right.full && left.height == right.height
);
}
public boolean isFullCompare(BiNode node) {
if (node == null) {
return true;
}
Queue<BiNode> queue = new LinkedList<>();
queue.add(node);
BiNode end = node, nextEnd = null;
int num = 0, level = 0;
while (!queue.isEmpty()) {
BiNode n = queue.poll();
num++;
if (n.left != null) {
queue.add(n.left);
nextEnd = n.left;
}
if (n.right != null) {
queue.add(n.right);
nextEnd = n.right;
}
if (n == end) {
level++;
end = nextEnd;
}
}
return num == (((int) Math.pow(2, level)) - 1);
}
@Test
public void test2() {
for (int i = 0; i < 10000; i++) {
BiNode node = Reduce.binaryTree(20, 100);
boolean r1 = isFull(node);
boolean r2 = isFullCompare(node);
if (r1 != r2) {
System.out.println(Printer.print(node));
System.out.println(r1);
System.out.println(r2);
return;
}
}
}
|