题目描述
思路解析动画文字版
记住「先剪左右子树，再判自己：值 0 且左右都空才剪」，下面每帧都在套它。
准备 · 后序 DFS：后序遍历从根出发，一路下探到最底层的叶子，再自底向上逐个判定去留。紫色=正在看，绿色=保留，红色=剪掉。
下行 · 根：后序下行到「根」（值 1）。先不急着判它，先把它的左、右子树都处理完。
下行 · 根·左：后序下行到「根·左」（值 0）。先不急着判它，先把它的左、右子树都处理完。
下行 · 根·左·左：后序下行到「根·左·左」（值 0）。先不急着判它，先把它的左、右子树都处理完。
下行 · 根·左·左·左：后序下行到「根·左·左·左」（值 0）。先不急着判它，先把它的左、右子树都处理完。
判定 · 剪掉 根·左·左·左：回到「根·左·左·左」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
下行 · 根·左·左·右：后序下行到「根·左·左·右」（值 0）。先不急着判它，先把它的左、右子树都处理完。
判定 · 剪掉 根·左·左·右：回到「根·左·左·右」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
判定 · 剪掉 根·左·左：回到「根·左·左」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
下行 · 根·左·右：后序下行到「根·左·右」（值 1）。先不急着判它，先把它的左、右子树都处理完。
判定 · 保留 根·左·右：回到「根·左·右」：它自己就是 1，保留（变绿色）。
判定 · 保留 根·左：回到「根·左」：它虽是 0，但子树里还留着 1（有孩子没被剪空），保留（变绿色）。
下行 · 根·右：后序下行到「根·右」（值 1）。先不急着判它，先把它的左、右子树都处理完。
下行 · 根·右·左：后序下行到「根·右·左」（值 0）。先不急着判它，先把它的左、右子树都处理完。
判定 · 剪掉 根·右·左：回到「根·右·左」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
下行 · 根·右·右：后序下行到「根·右·右」（值 0）。先不急着判它，先把它的左、右子树都处理完。
判定 · 剪掉 根·右·右：回到「根·右·右」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
判定 · 保留 根·右：回到「根·右」：它自己就是 1，保留（变绿色）。
判定 · 保留 根：回到「根」：它自己就是 1，保留（变绿色）。
完成：剪枝完成：绿色是保留下来的树，红色子树全被剪掉。注意「根·右」自己是 1，所以即便它两个 0 孩子被剪，它本身仍保留。
边界先想清：单 0 剪空、单 1 保留、全 0 全剪。
面试重点：剪枝 ⟺ 自底向上传「子树是否含 1」。
参考代码
from typing import Optionalclass TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass Solution: def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: if root is None: return None root.left = self.pruneTree(root.left) root.right = self.pruneTree(root.right) if root.val == 0 and root.left is None and root.right is None: return None return root复杂度
- 时间：O(n)，每个节点后序访问一次
- 空间：O(h)，递归栈深 = 树高 h（最坏 O(n)）
易错点
面试追问把动画讲成自己的话
追问剪枝和「判断子树是否含 1」是什么关系？
追问能否原地修改而不新建节点？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树中距离为 K 的节点
LeetCode 863 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题