P4476.第3题-Prompt上下文信息精简:找出二叉树中的最大值子树
题目内容
描述: Prompt 应用面临的一个首要问题就是 Token 的长度和精确度问题，如何精简 Prompt 的 token 长度一直是大模型应用中的难题。假设 Prompt 的 token 序列是一颗二叉树，给定这样一颗二叉树，该二叉树的每个节点都有一个值，可以是正负值，也可以是 0 ，请返回该二又树的最大值子树。每颗子树的值为该子树所有节点值的和。
注意:
输入和输出数据的格式要求:(1)二叉树是完全二叉树;(2)二叉树节点数据是通过宽度优先搜索遍历获取;(3)遍历出的二叉树节点数据是以一维数组的形式存储。(4)如果一颗二叉树的左节点不存在，就以 null 补齐。
举例:如果节点 A 和 B 是兄弟节点，它们两个的父节点是 C ，A 无子节点，B 有子节点 D 和 E ，那么这棵树的数组为 tree=[C,A,B,null,null,D,E];如果 B 只有左子节点 D ，则 tree=[C,A,B,null,null,D] ; 如果 B 只有右子节点 E ,则 tree=[C,A,B,null,null,null,E];
示例1
输入:[3,2,5]
输出: [3,2,5]
示例2
输入: [−5,−1,3,null,null,4,7]
输出: [3,4,7]
示例3
输入: [5,−1,3,null,null,4,7]
输出: [5,null,3,null,null,4,7]
输入描述
输入:二叉树是一颗完全二叉树，节点数据是通过宽度优先搜索遍历的，以一维数组结构表示，null 代表为空的叶子节点。
以示例 2 为例，输入为 [−5,−1,3,null,null,4,7]，−1 节点虽然是叶子节点，但在完全二叉树中需要明确它的两个子节点，这两个子节点为 null 。
输出描述
输出:输出最大值子树，也以宽度优先搜索完全二叉树后的数组结构表示的方式作为输出。
以示例 2 为例，由于 [−5,−1,3] 该子树为负值，不应当与子树 [3,4,7] 合一起，所以 [3,4,7] 是最大子树。
以示例 3 为例，最大值子树是 [5,null,3,null,null,4,7]，根节点 5 的所有左子树节点用 null 补
齐。
样例1
输入
[-5,-1,3,null,null,4,7]
输出
[3,4,7]
说明
最大子树 max−sub−tree 是 [3,4,7]
样例2
输入
[-1,null,1,null,null,-1,-1,null,null,null,null,2,1,-3,-1,null,null,null,null,null,null,null,null,2,1,3,8]
输出
[1,-1,null,2,1,null,null,2,1,3,8]
说明
最大子树 max−sub−tree 是 [1,−1,null,2,1,null,null,2,1,3,8]
