力扣题目链接：https://leetcode.cn/problems/binary-tree-pruning/
给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。
返回移除了所有不包含 1 的子树的原二叉树。
节点 node 的子树为 node 本身加上所有 node 的后代。
示例 1：
输入：root = [1,null,0,0,1] 输出：[1,null,0,null,1] 解释： 只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
示例 2：
输入：root = [1,0,1,0,0,0,1] 输出：[1,null,1,null,1]
示例 3：
输入：root = [1,1,0,1,1,0,1,0] 输出：[1,1,0,1,1,null,1]
提示：
- 树中节点的数目在范围 [1, 200] 内
- Node.val 为 0 或 1
递归，返回结果的同时进行修剪。
因为涉及到一个节点的所有子树，因此很适合深搜DFS。
构建一个函数isZero，用来判断一个节点是否是某个全0子树的根。同时，如果这个节点的左子树是全0子树，就剪掉这个节点的左子树；右子树同理。
bool isZero(TreeNode* root) {
bool is0 = true; // 这个节点是否为全0子树的根
if (root->val) // 如果这个节点的值为1
is0 = false; // 直接排除全0子树
// 判断左子树是否为全0子树。如果是，就修剪之
if (root->left) { // 前提是左子树不空
if (isZero(root->left)) { // 左子树是全0子树
root->left = nullptr; // 左子树设置为空（这样就修剪掉了）
}
else { // 左子树不是全0子树
is0 = false; // 那么“父树”更不是全0树
}
}
// 右子树同理
if (root->right) {
if (isZero(root->right)) {
root->right = nullptr;
}
else {
is0 = false;
}
}
return is0;
}
- 时间复杂度 O ( N ) O(N) O(N)，其中 N N N是节点的个数
- 空间复杂度 O ( N ) O(N) O(N)，空间复杂度主要来自递归
class Solution {
private:
bool isZero(TreeNode* root) {
bool is0 = true;
if (root->val)
is0 = false;
if (root->left) {
if (isZero(root->left)) {
root->left = nullptr;
}
else {
is0 = false;
}
}
if (root->right) {
if (isZero(root->right)) {
root->right = nullptr;
}
else {
is0 = false;
}
}
return is0;
}
public:
TreeNode* pruneTree(TreeNode* root) {
if (isZero(root))
root = nullptr;
return root;
}
};
同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/125918905
