在一次 Prompt 工程实践中,我们把一段 token 序列抽象成一棵二叉树。树中每个结点都有一个整数权值(可正可负,也可能为 0)。请在这棵树中选出一棵“价值最大”的子树,并把这棵子树按“完全二叉树的层序数组”形式输出。 子树的价值定义为它所包含的所有结点权值之和。 允许对某个结点“剪掉”对总和贡献为负的整棵子树(即可以只要左子树、或只要右子树、或两者都要;被剪掉的位置在输出中以 null 占位)。 输入是一棵“用层序数组表示的完全二叉树”,缺失位置用 null 占位;输出也使用相同规则表示挑选出的那棵最优子树,并且去除末尾多余的尾部 null。
输入描述:
一行:用方括号包裹的一维数组,表示树的层序遍历;缺失结点用 `null`。例如:`[5,-1,3,null,null,4,7]`。约定:1.数组下标从 0 开始;对下标 i,左孩子为 2i+1,右孩子为 2i+2。2.仅当该位置不是 `null` 才视为存在结点。
输出描述:
一行:选择的“最大和子树”的层序数组表示(仍以 `null` 占位),并删除末尾无意义的连续 `null`。
示例1
说明
以 3 为根的子树和为 3+6+7=16;整棵树在剪掉负贡献的左侧后,总和为 1+16=17,为全局最大。按完全二叉树层序输出时,左子树位置及其两个孩子以 null 占位。
加载中...