B站【23秋招】Java开发工程师-第一批（第二题）

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);
    }
}