814. 二叉树剪枝（Binary Tree Pruning）
难度：中等 | 主题：二叉树、递归、后序遍历
题目
给你二叉树的根节点 root，每个节点值都是 0 或 1。请剪去所有节点值都为 0 的子树（即不含 1 的子树），返回剪枝后的树根。
示例
输入：root = [1,null,0,0,1]
输出：[1,null,0,null,1]
解释：
1 1
\ → \
0 0
/ \ \
0 1 1
思路
先讲个故事：修剪枯枝
想象一棵盆栽，绿色枝条代表 1，枯黄枝条代表 0。你想剪掉所有完全没有绿叶的分支。
你从树梢开始检查：
-
先看最末端的细枝——如果全是枯黄（0），咔嚓剪掉
-
再看上一级——如果左右两边的细枝都被剪光了，而且这根也枯黄，那它也要剪掉
-
不断往上推，直到根
这不就是后序遍历吗？——先处理子树，再决定当前节点。
引导式推导：自底向上做决定
核心规则：一个节点该不该剪？
当且仅当：节点值 = 0 且 左右子树都被剪没了（都是空）
因为：
-
节点值 = 1 → 子树含 1，怎么都不能剪
-
左右子树有 1 → 子树含 1，不能剪
-
左右子树还有值 → 子树还有节点，等它们被处理后再说
为什么必须是后序？
前序：先看父节点 → 不知道子树有没有 1，无法决定
中序：先看左子树 → 看了父节点才看右子树，也是错
后序：先看子树 → 子树的结果决定了当前节点要不要留
后序的核心思想：子问题先解决，父问题的答案依赖子问题的结果。
递归自顶向下的视角
pruneTree(root):
1. 递归剪左子树 → root.left = 结果
2. 递归剪右子树 → root.right = 结果
3. 如果 root.val == 0 且左右子树都被剪空了：
返回 None（剪掉自己）
否则返回 root（保留）
每一步的返回值就是”剪枝后这棵子树长什么样”。
父节点直接接住返回值就完成了剪枝——接住即剪掉。
代码
def pruneTree(self, root):
# 空节点：不需要处理
if not root:
return None
# 后序：先递归剪掉左右子树中不含 1 的分支
root.left = self.pruneTree(root.left)
root.right = self.pruneTree(root.right)
# 后序位置：处理完子树后判断当前节点
# 剪枝条件：自己是 0 且左右都被剪空了 → 以自己为根的子树不含 1
if root.val == 0 and not root.left and not root.right:
return None # 剪掉
return root # 保留
为什么 root.left = self.pruneTree(root.left) 能自动完成剪枝？
因为 pruneTree 返回剪枝后的子树根。如果左子树全被剪了，返回 None，root.left = None。如果左子树还有东西，返回左子树的根，root.left = 原来的左子树根。一句赋值同时实现了”剪掉”和”保留”两种效果。
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 时间 | O(n) | 每个节点访问一次 |
| 空间 | O(h) | 递归栈深度，最坏 O(n)（链），平均 O(log n) |
实战考量
频率分析
出现在：字节/美团/百度 二叉树后序应用题，低频但典型。考察”后序思维”——你能不能意识到必须先知道子树的情况才能决定当前节点。
延伸思考
Q：为什么不能用前序遍历？
A：前序是先处理当前节点再递归子树。但剪枝决策依赖子树结果——你不知道左右子树还有没有 1，就无法判断当前节点是否该剪。前序硬写的话需要额外传递状态信息，逻辑会复杂很多。
Q：剪枝策略的数学归纳法证明？
A：
-
基础：叶节点为 0 → 被剪掉（返回 None）
-
归纳：非叶节点，左右子树都返回 None 且自身为 0 → 被剪掉
-
结论：剪枝后，树中任意子树至少包含一个值为 1 的节点
Q：迭代版怎么做？
A：用栈做后序遍历。需要标记节点访问状态（第一次访问 vs 处理完左右子树）。处理逻辑和递归一样，但要手动维护栈和状态。
Q：如果要求剪掉所有值为 0 的节点（不管子树有没有 1）？
A：那就是”删除所有值为 0 的节点”，不是剪枝。同样是后序，但剪枝条件变成 root.val == 0 就删，不判断左右子树。但要注意删掉后父节点的左/右指针要更新。
Q：如果节点值可以是任何整数，剪掉所有和为 0 的子树？
A：同样后序框架。pruneTree 返回 (剪枝后的子树, 子树和)。(子树和, 剪枝后左右子树) → 如果子树和为 0 且当前节点也被剪后子树和为 0 → 剪掉。
易错点
-
必须后序，前序/中序不行
-
剪枝条件 =
val == 0且左右子树都为空 -
root.left = self.pruneTree(root.left)要接住返回值，否则剪了等于没剪 -
空节点直接返回 None，不进入剪枝判断
生活类比
剪枝 → 修剪盆栽
后序剪枝就像从树梢开始检查：先看最细的枝条（叶节点），枯了就剪；
回到上一级，如果两边细枝都剪了，这根粗枝也枯了，那就整根剪掉。
一直剪到主干——如果整棵树都是枯的（全是 0），最后返回 None 表示”这盆花没救了，扔掉”。
相关题目
| 题目 | 关系 |
|---|---|
| 337打家劫舍III | 同是后序遍历，不过加 DP |
| 104二叉树的最大深度 | 后序基础框架 |
| 110平衡二叉树 | 后序 + 高度判断，同框架 |
→ 返回题单：LeetCode学习路线图 > 五、二叉树
速记卡（面试闪卡）
Q1：一句话讲清「814. 二叉树剪枝（Binary Tree Pruning）」到底是什么？
A：剪掉所有不含 1 的零值子树，后序遍历、自己是 0 且左右皆空才删。
Q2：题目理解 —— 什么算该剪的枝？ —— 怎么理解？
A：像修剪盆栽：只剪完全没绿叶（不含 1）的枯枝。含 1 的再小也要留。英文：Binary Tree Pruning。
Q3：核心思路 —— 为什么必须后序？ —— 怎么理解？
A：像从树梢往上查：先看细枝枯没枯，再决定粗枝。父节点留不留取决于子树结果，所以先处理子树。英文：Post-order Decision。
Q4：代码实现 —— 一句赋值怎么剪？ —— 怎么理解？
A：像接住下属交回的盆栽：root.left = prune(左) 直接接返回值，返回 None 即剪掉、返回根即保留。英文：Return-as-Cut。
Q5：复杂度与实战 —— 前序为何不行？ —— 怎么理解？
A：像没看完子树就下刀：前序不知左右还有没有 1，无法决策。时间 O(n)、空间 O(h)。英文：Top-down Fail。
Q6：核心速记主线有哪些？
-
剪枝条件：节点值=0 且左右子树都为空才删
-
必须后序：先递归处理左右，再决定当前节点
-
用 root.left = prune(root.left) 接住返回值即完成剪/留
-
前序/中序不行，决策依赖子树结果
-
空节点直接返回 None，不进入判断
口诀
A：枯枝含一不须剪，
后序自底定去留；
接住返回值即断，
空树归还无一筹。