哔哩哔哩9.1笔试题解+注释
1. 小红的链表结点合并
public static class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
}
public static ListNode mergeNode(ListNode head) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0), cur = dummy;
while (head != null && head.next != null) {
int a = head.val;
head = head.next;
int b = head.val;
cur.next = new ListNode(a * b);
cur = cur.next;
head = head.next;
}
return dummy.next;
} 2.小红的最大层权值
前置知识：怎么判断一棵树是否是平衡二叉树
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return process(root) >= 0;
}
public int process(TreeNode x) {
if (x == null) {
return 0;
}
int left = process(x.left);
int right = process(x.right);
if (left >= 0 && right >= 0 && Math.abs(left - right) <= 1) {
return Math.max(left, right) + 1;
} else {
return -1;
}
} public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public static int maxValue(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// 深度
int deep = 0;
// income[i]代表第i层通过交换能获得的最大收益，默认为0
int maxDeep = maxDeep(root);
int[] income = new int[maxDeep];
int[] sums = new int[maxDeep];
// bfs
while (!queue.isEmpty()) {
int size = queue.size();
// 这一层的权值和
int curSum = 0;
for (int i = 0; i < size; i++) {
// 遍历这一层的所有结点
TreeNode x = queue.poll();
// 统计这一层的权值和
curSum += x.val;
// 当前到达第n层
// case 1: x结点 与 n + 1 层自己的左右结点交换，能给 第 n 层的带来最大收益。
// case 2: x结点 与 n + 1 层自己的左右结点交换，能给 第 n + 1 层的带来最大收益。
// case 1
// 当前结点和左孩子交换获得的收益（左孩子.val - x.val）
int leftInCome = 0;
if (x.left != null) {
leftInCome = x.left.val - x.val;
queue.add(x.left);
}
// 当前结点和右孩子交换获得的收益
int rightInCome = 0;
if (x.right != null) {
rightInCome = x.right.val - x.val;
queue.add(x.right);
}
// 存入income数组中，代表第deep层通过交换能获得的最大收益
int curMax = Math.max(0, Math.max(leftInCome, rightInCome));
income[deep] = Math.max(income[deep], curMax);
// case 2
// x结点换到自己的左孩子交换获取的收益（x.val - 左孩子.val）
if (deep + 1 != maxDeep) {
leftInCome = -leftInCome;
rightInCome = -rightInCome;
int curMax2 = Math.max(0, Math.max(leftInCome, rightInCome));
income[deep + 1] = Math.max(income[deep + 1], curMax2);
}
}
// 遍历完一层，深度 + 1。同时记录这一层的权值和
sums[deep++] = curSum;
}
// 遍历sums数组
int res = 0;
for (int i = 0; i < sums.length; i++) {
res = Math.max(res, sums[i] + income[i]);
}
return res;
}
// 返回二叉树的最大深度
public static int maxDeep(TreeNode x) {
if (x == null) {
return 0;
}
return Math.max(maxDeep(x.left), maxDeep(x.right)) + 1;
}
3. 平衡二叉树
public static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
static PriorityQueue<TreeNode> queue = new PriorityQueue<>((t1, t2) -> {
// 获取t1、t2的结点个数
int nodes1 = treeNodes(t1);
int nodes2 = treeNodes(t2);
if (nodes1 == nodes2) {
// 如果结点个数相同，按照子树的头结点从小到大排序
return t1.val - t2.val;
} else {
// 如果结点个数不同，按照结点数量从小到大排序
return nodes1 - nodes2;
}
});
public static TreeNode[] balanceSubTree(TreeNode root) {
if (root == null) {
// base case
return new TreeNode[]{};
}
// 后序遍历
process(root);
// 最后加入剩下的头结点
queue.add(root);
TreeNode[] ret = new TreeNode[queue.size()];
int index = 0;
while (!queue.isEmpty()) {
ret[index++] = queue.poll();
}
return ret;
}
private static int process(TreeNode x) {
if (x == null) {
return 0;
}
int left = process(x.left);
int right = process(x.right);
if (left >= 0 && right >= 0 && Math.abs(left - right) <= 1) {
// 如果左树是平衡二叉树并且右树是平衡二叉树，并且左树右树高度差不超过1，那么这棵树是平衡二叉树
// 返回最大高度
return Math.max(left, right) + 1;
} else {
// 不是平衡二叉树，需要拆分。
if (left > right) {
// 如果左树高度大于右树高度
// 左树无论如何都要加入的
queue.add(x.left);
// 置空x的左树
x.left = null;
// 这里就分为两种情况，第一种情况右树高度小于等于1。第二种情况右树高度大于1
// case1：右树高度小于等于1，那么这棵树高度为0或者为1，都可以和当前头结点构成平衡二叉树。不用单独将右树加入返回结果
// case2: 右树高度大于1，也就是大于等于2，因为左树已经置空了，当前头结点加上这个高度大于等于2的子树，构成不了平衡二叉树。所以直接将右树加入
if (right <= 1) {
// case 1 右树不需要单独处理，返回当前头结点 + 右树高度
return right + 1;
} else {
// case 2 右树需要单独处理，返回头结点的高度，也就是1
queue.add(x.right);
x.right = null;
return 1;
}
} else {
// 左树高度小于右树高度，情况分析和上面一样
queue.add(x.right);
// 置空x的右树
x.right = null;
if (left <= 1) {
// case 1
return left + 1;
} else {
// case 2
queue.add(x.left);
x.left = null;
return 1;
}
}
}
}
// 返回一棵树的结点个数
public static int treeNodes(TreeNode x) {
if (x == null) {
return 0;
}
return treeNodes(x.left) + treeNodes(x.right) + 1;
} 
