会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
整体分三步：还原二叉树 → 非递归后序处理（先规则一切除、后规则二归并）→ 层序输出并统计节点数与深度。
还原二叉树。 节点净功率取值两两不同，先用中序序列建立「值 → 中序下标」的映射。用显式栈模拟递归：栈帧记录当前子树在前序中的起点 pl、中序区间 [il, ir]、父节点编号 par 以及自己是父节点的左孩子还是右孩子。弹出一帧后，前序起点的值就是当前子树的根，查映射得到它在中序中的位置 k，左子树大小为 k - il，于是左子树对应前序 [pl+1, pl+k-il]、中序 [il, k-1]，右子树对应前序 [pl+k-il+1, ...]、中序 [k+1, ir]。把两个子问题压栈即可，避免递归在链状树上爆栈。直接用中序下标当节点编号，节点值就是中序序列本身。
规则一（越限隔离）。 用带状态位的显式栈做后序遍历：栈帧 (u, par, side, state)，state=0 表示首次进入，state=1 表示左右子树都已处理完。进入 u 时先算供电裕度 s(u)=s(par)+val(u)：若 s(u)<L 或 s(u)>R，直接把父节点指向 u 的指针置空（若 u 是根则整棵树置空），并不再展开它的后代，这就等价于「整棵子树一次性切除」；否则压入 state=1 帧和两个孩子的 state=0 帧。由于 state=1 帧先于孩子帧入栈、后于孩子帧出栈，规则一必然在每个节点的归并之前完成。
规则二（串联归并）。 在 state=1 帧里对 u 循环判断：若 u 恰好有一个孩子 c（没有孩子或有两个孩子都停止），且 u 与 c 同号（都大于 0 或都小于 0；只要有一方为 0 就视为不同号），则把 c 的值加到 u 上，并让 u 继承 c 的左右孩子，然后继续用新的值重复判断。每次归并都让树上少一个节点，总归并次数不超过 n，不会退化。
