如何剪掉二叉树中路径和不足的节点？为什么要自底向上判断？

简化版

剪掉路径和不足的节点要判断“从根到叶的每条路径是否满足限制”。递归时累计当前路径和，到叶子判断是否达标；回溯时如果某个节点的左右子树都被剪掉，说明它不在任何有效路径上，也要剪掉。

详细版

这类题的关键是：节点是否保留，取决于它是否属于至少一条合格的根到叶路径。

常见递归：

从根开始累计路径和。
到叶子时判断 sum >= limit。
如果叶子不达标，返回 null。
递归剪左子树和右子树。
如果剪完后当前节点没有孩子，且它不是合格叶子路径的一部分，返回 null。

更简洁的写法是把 limit 逐层减去当前值，到叶子判断剩余限制是否满足。

完整版教学

一、为什么不能只看节点当前路径和

一个中间节点路径和不足，不代表它一定要删除，因为后面可能还有大值节点把总和补回来。反过来，一个中间节点当前路径和很高，也不代表它能保留，因为所有到叶子的路径可能最终都不达标。

判断标准是：

节点保留 ⇔ 它位于至少一条满足 limit 的根到叶路径上

这个定义天然依赖子树结果，不能只在自顶向下时立刻决定。

二、叶子节点为什么是判定终点

路径和题通常要求根到叶路径。只有到叶子时，一条完整路径才形成。中间节点不是完整路径终点。

例如 limit=10：

root到当前 = 6
后面还有 5，最终 11，应该保留

所以递归到叶子再判断是否达标。叶子不达标就删除，叶子达标就保留，并让父节点知道这条路径有效。

三、为什么要自底向上剪枝

父节点是否保留，取决于左右子树是否还存在有效路径。如果左右子树都被剪空，父节点也不在任何有效根到叶路径上。

left = prune(left)
right = prune(right)
if left == null && right == null && 当前不能作为有效叶子:
  删除当前

这就是后序思想：先让孩子告诉你有没有有效路径，再决定当前节点去留。

四、递归参数怎么设计

有两种常见设计。一种传累计和，一种传剩余 limit。

// 剩余 limit 写法
function prune(node, limit) {
  if (!node) return null;
  limit -= node.val;
  if (!node.left && !node.right) {
    return limit <= 0 ? node : null;
  }
  node.left = prune(node.left, limit);
  node.right = prune(node.right, limit);
  return (!node.left && !node.right) ? null : node;
}

剩余 limit 的好处是叶子处只看 limit <= 0，不用额外维护完整 sum。

五、负数节点会带来什么坑

如果节点值可能为负，不能看到当前 sum 已经大于 limit 就提前保留，也不能看到当前 sum 小于 limit 就提前删除。后续路径可能下降或上升。

当前状态	能否提前判断	原因
当前 sum 不足	不能删	后续可能有正数
当前 sum 达标	不能直接保留	后续可能有负数且必须到叶
到叶后达标	可以保留	完整路径成立

因此最稳的判断点仍然是叶子。

六、复杂度和返回语义

每个节点访问一次，时间 O(n)。递归栈空间 O(h)。返回 null 表示这棵子树没有任何有效路径，返回 node 表示至少有一条有效路径保留。

记忆钩子：剪路径和不足的树，不是剪“当前不够”的节点，而是剪“不属于任何合格根到叶路径”的节点。

七、常见误区与追问

误区：中间路径和小于 limit 就立即删除。 后续节点可能补足路径和，不能提前删。
误区：当前路径和达到 limit 就一定保留。 必须走到叶子，且后续可能有负数。
误区：只删叶子不回头处理父节点。 子树被删光后父节点也可能失去有效路径。
追问：为什么用后序？ 父节点是否保留依赖左右子树剪枝后的结果。
追问：复杂度是多少？ 时间 O(n)，递归栈 O(h)，原地修改树结构。

八、加强记忆

这题的核心定义是“保留属于有效根到叶路径的节点”。有效性只能在叶子确认，父节点要等孩子剪完后才知道自己还有没有有效路径。自顶向下传路径信息，自底向上返回保留结果，是这类剪枝题的标准框架。

简化版

详细版