LeetCode 814中等树/DFS
二叉树剪枝 图解题解
这道题到底在问什么
给定二叉树 root（节点值为 0 或 1），删除所有不包含 1 的子树（即子树里全是 0），返回剪枝后的根节点。
- 输入
- root=[1,null,0,0,1]
- 输出
- [1,null,0,null,1] （左侧全 0 的叶子被剪）
最优解：一步一步想明白
- 3记住「先剪左右子树，再判自己：值 0 且左右都空才剪」，下面每帧都在套它。
- 4从根下行后序遍历从根出发，一路下探到最底层的叶子，再自底向上逐个判定去留。紫色=正在看，绿色=保留，红色=剪掉。
- 5访问 根（值 1）后序下行到「根」（值 1）。先不急着判它，先把它的左、右子树都处理完。
- 6访问 根·左（值 0）后序下行到「根·左」（值 0）。先不急着判它，先把它的左、右子树都处理完。
- 7访问 根·左·左（值 0）后序下行到「根·左·左」（值 0）。先不急着判它，先把它的左、右子树都处理完。
- 8访问 根·左·左·左（值 0）后序下行到「根·左·左·左」（值 0）。先不急着判它，先把它的左、右子树都处理完。
- 9剪掉 根·左·左·左回到「根·左·左·左」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
- 10访问 根·左·左·右（值 0）后序下行到「根·左·左·右」（值 0）。先不急着判它，先把它的左、右子树都处理完。
- 11剪掉 根·左·左·右回到「根·左·左·右」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
- 12剪掉 根·左·左回到「根·左·左」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
- 13访问 根·左·右（值 1）后序下行到「根·左·右」（值 1）。先不急着判它，先把它的左、右子树都处理完。
- 14保留 根·左·右回到「根·左·右」：它自己就是 1，保留（变绿色）。
- 15保留 根·左回到「根·左」：它虽是 0，但子树里还留着 1（有孩子没被剪空），保留（变绿色）。
- 16访问 根·右（值 1）后序下行到「根·右」（值 1）。先不急着判它，先把它的左、右子树都处理完。
- 17访问 根·右·左（值 0）后序下行到「根·右·左」（值 0）。先不急着判它，先把它的左、右子树都处理完。
- 18剪掉 根·右·左回到「根·右·左」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
- 19访问 根·右·右（值 0）后序下行到「根·右·右」（值 0）。先不急着判它，先把它的左、右子树都处理完。
- 20剪掉 根·右·右回到「根·右·右」：它自己是 0，左右子树也都已剪空——整棵子树里没有一个 1，整棵剪掉（变红色）。
- 21保留 根·右回到「根·右」：它自己就是 1，保留（变绿色）。
- 22保留 根回到「根」：它自己就是 1，保留（变绿色）。
- 23剪枝结束剪枝完成：绿色是保留下来的树，红色子树全被剪掉。注意「根·右」自己是 1，所以即便它两个 0 孩子被剪，它本身仍保留。
⚠️ 容易写错的地方
✗ 错：只看节点自己是不是 0 就剪
✓ 对：要看「整棵子树」有没有 1
一个 0 节点若有含 1 的后代，必须保留
✗ 错：用前序/中序判定
✓ 对：必须后序（先剪孩子再判父）
父的去留依赖孩子剪枝后的结果，顺序错就判错
✗ 错：忘了把递归结果赋回 root.left/right
✓ 对：root.left = prune(root.left)
不赋回则被剪的子树没真正断开
完整代码（Python / C++ / Java）
Python
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class 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 rootC++
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if (!root) return nullptr;
root->left = pruneTree(root->left);
root->right = pruneTree(root->right);
if (root->val == 0 && !root->left && !root->right) return nullptr;
return root;
}
};Java
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; }
}
class Solution {
public TreeNode pruneTree(TreeNode root) {
if (root == null) return null;
root.left = pruneTree(root.left);
root.right = pruneTree(root.right);
if (root.val == 0 && root.left == null && root.right == null) return null;
return root;
}
}复杂度
时间
O(n)
每个节点后序访问一次
空间
O(h)
递归栈深 = 树高 h（最坏 O(n)）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉树剪枝 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
剪枝和「判断子树是否含 1」是什么关系？+
本质是同一件事的两种表述。prune 函数返回非空 ⟺ 子树含 1。递归里「root.val==1 或 左子树含1 或 右子树含1」就保留，否则剪掉。把它想成「自底向上传递『我这棵子树有没有 1』这个布尔信息」就清楚了。
能否原地修改而不新建节点？+
可以，本解就是原地：把递归结果赋回 root.left/root.right，被剪的子树指针置 null 即断开，不额外分配节点，空间只有递归栈 O(h)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 二叉树剪枝 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。