Medium

题目描述

给你二叉树的根结点 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

解题思路

这是一道经典的二叉树递归题目。核心思想是通过后序遍历（先处理子树，再处理当前节点）来判断每个子树是否包含1。

算法思路：

  1. 递归处理左右子树：对于每个节点，先递归处理其左右子树，剪除不包含1的子树
  2. 判断当前子树是否需要保留：一个子树需要保留当且仅当：
    • 当前节点值为1，或者
    • 左子树或右子树中至少有一个包含1
  3. 返回结果：如果当前子树不包含1，返回null；否则返回当前节点

具体实现：

  • 使用递归函数，返回值表示处理后的子树根节点
  • 对于每个节点，先递归处理左右子树
  • 如果当前节点值为0且左右子树都为空（即都被剪除），则当前节点也应该被剪除
  • 否则保留当前节点，更新其左右子树为递归处理的结果

这种方法的优势是一次遍历就能完成剪枝操作，逻辑清晰，代码简洁。

代码实现

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;
    }
};

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None
        
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        
        if root.val == 0 and not root.left and not root.right:
            return None
        
        return root

public 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;
    }
}

var pruneTree = function(root) {
    if (!root) return null;
    
    root.left = pruneTree(root.left);
    root.right = pruneTree(root.right);
    
    if (root.val === 0 && !root.left && !root.right) {
        return null;
    }
    
    return root;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历树中的每个节点一次
空间复杂度O(h)递归调用栈的深度，h为树的高度，最坏情况下为O(n)