1. 判断是否是平衡二叉树
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
class Info {
public int height;
public boolean balanced;
public Info(int height, boolean balanced) {
this.height = height;
this.balanced = balanced;
}
}
public boolean isBalanced(BiNode node) {
if (node == null) {
return true;
}
return processBalance(node).balanced;
}
private Info processBalance(BiNode node) {
if (node == null) {
return new Info(0, true);
}
Info leftInfo = processBalance(node.left);
Info rightInfo = processBalance(node.right);
return new Info(
Math.max(leftInfo.height, rightInfo.height) + 1,
leftInfo.balanced && rightInfo.balanced && Math.abs(leftInfo.height - rightInfo.height) <= 1
);
}
public boolean isBalancedCompare(BiNode node) {
boolean[] ans = new boolean[1];
ans[0] = true;
processBalance1(node, ans);
return ans[0];
}
private int processBalance1(BiNode node, boolean[] ans) {
if (!ans[0]) {
return -1;
}
if (node == null) {
return 0;
}
int l = processBalance1(node.left, ans);
int r = processBalance1(node.right, ans);
if (Math.abs(l - r) > 1) {
ans[0] = false;
}
return Math.max(r, l) + 1;
}
@Test
public void test1() {
for (int i = 0; i < 10000; i++) {
BiNode node = Reduce.binaryTree(5, 100);
boolean r1 = isBalanced(node);
boolean r2 = isBalancedCompare(node);
if (r1 != r2) {
System.out.println(Printer.print(node));
System.out.println(r1);
System.out.println(r2);
return;
}
}
}
2. 判断树是否是搜索二叉树
任一一棵子树， 左树的所有节点都比根节点小，右树所有节点都比根节点大
class Info1 {
public boolean isSearch;
public int max;
public int min;
public Info1(boolean isSearch, int max, int min) {
this.isSearch = isSearch;
this.max = max;
this.min = min;
}
}
public boolean isSearchTree(BiNode node) {
if (node == null) {
return true;
}
return processSearch(node).isSearch;
}
private Info1 processSearch(BiNode node) {
if (node == null) {
return new Info1(true, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
Info1 left = processSearch(node.left);
Info1 right = processSearch(node.right);
return new Info1(
left.isSearch && right.isSearch
&& left.max < node.value && right.min > node.value,
Math.max(left.max, Math.max(right.max, node.value)),
Math.min(Math.min(right.min, left.min), node.value)
);
}
public int isSearchTreeCompare(BiNode node) {
if (node == null) {
return 0;
}
Stack<BiNode> nodes = new Stack<>();
BiNode curr = node;
int res = 0;
int max = Integer.MIN_VALUE;
while ((curr != null || !nodes.isEmpty())) {
if (curr == null) {
curr = nodes.pop();
res++;
if (curr.value <= max) {
return -1;
}
max = curr.value;
curr = curr.right;
continue;
}
nodes.push(curr);
curr = curr.left;
}
return res;
}
@Test
public void test2() {
for (int i = 0; i < 10000; i++) {
BiNode node = Reduce.binaryTree(10, 100);
boolean r1 = isSearchTree(node);
boolean r2 = isSearchTreeCompare(node) >= 0;
if (r1 != r2) {
System.out.println(Printer.print(node));
System.out.println(r1);
System.out.println(r2);
return;
}
}
}
4. 求两节点之间的最大距离
给定一个头结点head， 任何两个基点之间都存在距离，返回整颗二叉树的最大距离
class Info2 {
public int height;
public int maxLength;
public Info2(int height, int maxLength) {
this.height = height;
this.maxLength = maxLength;
}
}
public int maxDistance(BiNode node) {
if (node == null) {
return 0;
}
return processDistance(node).maxLength;
}
private Info2 processDistance(BiNode node) {
if (node == null) {
return new Info2(0, 0);
}
Info2 left = processDistance(node.left);
Info2 right = processDistance(node.right);
return new Info2(
Math.max(left.height, right.height) + 1,
Math.max(Math.max(left.maxLength, right.maxLength),
left.height + right.height + 1)
);
}
public int maxDistanceCompare(BiNode node) {
if (node == null) {
return 0;
}
int max = 1;
Map<BiNode, BiNode> node2parent = new HashMap<>();
Stack<BiNode> stack = new Stack<>();
stack.push(node);
while (!stack.isEmpty()) {
BiNode n = stack.pop();
if (n.left != null) {
node2parent.put(n.left, n);
stack.push(n.left);
}
if (n.right != null) {
node2parent.put(n.right, n);
stack.push(n.right);
}
}
List<BiNode> array = new ArrayList<>(node2parent.keySet());
array.add(node);
for (int i = 0; i < array.size() - 1; i++) {
for (int j = i + 1; j < array.size(); j++) {
max = Math.max(max, distance(array.get(i), array.get(j), node2parent));
}
}
return max;
}
private int distance(BiNode node, BiNode node1, Map<BiNode, BiNode> node2parent) {
Set<BiNode> set = new HashSet<>();
BiNode p1 = node, p2 = node1;
while (p1 != null) {
set.add(p1);
p1 = node2parent.get(p1);
}
while (p2 != null) {
if (!set.add(p2)) {
break;
}
p2 = node2parent.get(p2);
}
while (p2 != null) {
p2 = node2parent.get(p2);
if (p2 != null) {
set.remove(p2);
}
}
return set.size();
}
@Test
public void test4() {
for (int i = 0; i < 100000; i++) {
BiNode node = Reduce.binaryTree(20, 100);
int r1 = maxDistance(node);
int r2 = maxDistanceCompare(node);
if (r1 != r2) {
System.out.println(Printer.print(node));
System.out.println(r1);
System.out.println(r2);
return;
}
}
}
5. 找出树中，最大的搜索二叉树节点个数
class Info3 {
public int nodeNum;
public int min;
public int max;
public int maxBSTSubTreeNum;
public Info3(int nodeNum, int min, int max, int maxBSTSubTreeNum) {
this.nodeNum = nodeNum;
this.min = min;
this.max = max;
this.maxBSTSubTreeNum = maxBSTSubTreeNum;
}
}
public Info3 processMaxBSTNumber(BiNode node) {
if (node == null) {
return new Info3(0, Integer.MAX_VALUE, Integer.MIN_VALUE, 0);
}
Info3 left = processMaxBSTNumber(node.left);
Info3 right = processMaxBSTNumber(node.right);
boolean leftBST = left.maxBSTSubTreeNum == left.nodeNum;
boolean rightBST = right.maxBSTSubTreeNum == right.nodeNum;
int maxNum = Math.max(right.maxBSTSubTreeNum, left.maxBSTSubTreeNum);
if (leftBST && rightBST && left.max < node.value && right.min > node.value) {
maxNum = right.nodeNum + left.nodeNum + 1;
}
return new Info3(
left.nodeNum + right.nodeNum + 1,
Math.min(Math.min(left.min, right.min), node.value),
Math.max(Math.max(left.max, right.max), node.value),
maxNum
);
}
public int maxBSTNum(BiNode node) {
return processMaxBSTNumber(node).maxBSTSubTreeNum;
}
public int maxBSTNumCompare(BiNode node) {
if (node == null) {
return 0;
}
int max = 0;
Queue<BiNode> queue = new LinkedList<>();
queue.add(node);
BiNode currEnd = node, nextEnd = null;
while (!queue.isEmpty()) {
BiNode n = queue.poll();
if (n.left != null) {
nextEnd = n.left;
queue.add(n.left);
}
if (n.right != null) {
nextEnd = n.right;
queue.add(n.right);
}
max = Math.max(max, isSearchTreeCompare(n));
if (n == currEnd) {
currEnd = nextEnd;
}
}
return max;
}
@Test
public void test5() {
for (int i = 0; i < 10000; i++) {
BiNode node = Reduce.binaryTree(10, 100);
int max1 = maxBSTNum(node);
int max2 = maxBSTNumCompare(node);
if (max1 != max2) {
System.out.println(Printer.print(node));
System.out.println(max1);
System.out.println(max2);
return;
}
}
}
二叉树递归套路
- 假设以×节点为头，假设可以向X左树和X右树要任何信息
- 在上一步的假设下，讨论以X为头节点的树，得到答案的可能性（最重要)
- 列出所有可能性后，确定到底需要向左树和右树要什么样的信息
- 把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息 S
- 递归函数都返回S，每一棵子树都这么要求
- 写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
|