B站【23秋招】Java开发工程师-第一批（第二题）
当然，肯定不是最优解，算是暴力破解，但是可以参考一下解题思路啦。
主要通过集合来记录了之前的数据信息，算了，我也不多说了，代码我都写了注释的，应该很好理解。
（题外话：包括第三题也是，可以通过 map 来记录当前节点的父节点，一旦发现不平衡，直接 map.get() 就可以获取父节点，随之做相关的处理）
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int maxValue (TreeNode root) {
// 队列记录第一层的节点
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
// 全局最大值（当前为跟节点的值）
int result = root.val;
// 更新全局最大值：与当前节点的左子节点做交换（如果左子节点的值更大）
if (root.left != null && root.left.val > result) result = root.left.val;
// 更新全局最大值：与当前节点的右子节点做交换（如果右子节点的值更大）
if (root.right != null && root.right.val > result) result = root.right.val;
// 递归执行
return getMaxValue(queue, result);
}
/**
* 递归执行
* @param queue 上一层级的节点
* @param result 全局最大值
* @return 全局最大值
*/
public int getMaxValue(Queue<TreeNode> queue, int result){
// 最终返回全局最大值
if (queue.isEmpty()) return result;
// 记录当前层的总权值
final int[] curScore = {0};
// 记录当前层的所有节点
Queue<TreeNode> curQueue = new ArrayDeque<>();
// 记录上一层的所有节点(方法传递进来的节点在使用后会转移到这个队列)
Queue<TreeNode> temp = new ArrayDeque<>();
// 遍历上层节点，将上层节点的字节点（当前层的节点加入到队列）
while (!queue.isEmpty()){
// 上一层的某个节点
TreeNode curNode = queue.poll();
// 如果有左节点，就加入到当前层节点队列
if (curNode.left != null) curQueue.add(curNode.left);
// 如果有右节点，就加入到当前层节点队列
if (curNode.right != null) curQueue.add(curNode.right);
// 转移上一层节点（因为结束的条件是队列为空，所以需要转移到另一个队列）
// 当然也可以再次加入到当前队列，但是需要记录对头的数据，判断如果回到对头就跳出循环即可
temp.add(curNode);
}
// 通过遍历当前层的所有节点得到当前层的权值之和
curQueue.forEach(treeNode -> curScore[0] += treeNode.val);
// 再次遍历上层节点（这里主要是为了做交换）
while (!temp.isEmpty()){
// 父节点（上一层的某个节点）
TreeNode preNode = temp.poll();
// 如果父节点（上一层的某个节点）存在左节点
if (preNode.left != null){
// 得到当前节点（当前层的某一个节点）
TreeNode curNode = preNode.left;
// 记录当前节点（准确的说是当前位置，因为这个位置的节点可以进行交换）的最大权值
int maxVal = curNode.val;
// 与父节点做交换（如果父节点的值更大）
if (preNode.val > maxVal) maxVal = preNode.val;
// 与当前节点的左子节点做交换（如果左子节点的值更大）
if (curNode.left != null && curNode.left.val > maxVal) maxVal = curNode.left.val;
// 与当前节点的右子节点做交换（如果右子节点的值更大）
if (curNode.right != null && curNode.right.val > maxVal) maxVal = curNode.right.val;
// 更新最大权值：当前层新的最大值 = 当前层旧的最大值 - 交换前节点的值 + 交换之后节点的值（当前位置的最大权值）
if (curScore[0] - curNode.val + maxVal > result) result = curScore[0] - curNode.val + maxVal;
}
// 如果父节点（上一层的某个节点）存在右节点 -> 与上一致
if (preNode.right != null){
TreeNode curNode = preNode.right;
int cnt = curNode.val;
if (preNode.val > cnt) cnt = preNode.val;
if (curNode.left != null && curNode.left.val > cnt) cnt = curNode.left.val;
if (curNode.right != null && curNode.right.val > cnt) cnt = curNode.right.val;
if (curScore[0] - curNode.val + cnt > result) result = curScore[0] - curNode.val + cnt;
}
}
// 将当前层的节点作为下一层的父节点，递归执行
return getMaxValue(curQueue, result);
}
}
