难度: Medium
给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。
节点 node 的子树为 node 本身，以及所有 node 的后代。
示例 1:
输入: [1,null,0,0,1] 输出: [1,null,0,null,1] 解释: 只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
示例 2:
输入: [1,0,1,0,0,0,1] 输出: [1,null,1,null,1] 解释:
示例 3:
输入: [1,1,0,1,1,0,1,0] 输出: [1,1,0,1,1,null,1] 解释:
提示:
[1,200]0 或 1注意：本题与主站 814 题相同：https://leetcode-cn.com/problems/binary-tree-pruning/
运行时间: 22 ms
内存: 16.0 MB
# Definition for a binary tree node.
# 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: TreeNode) -> TreeNode:
if not root:
return
root.left = self.pruneTree(root.left)
root.right = self.pruneTree(root.right)
if not root.left and not root.right and root.val == 0:
return None
return root
本题解采用递归方法来解决问题。递归函数 `pruneTree` 检查每个节点，如果一个节点的值为 0 并且它的左右子树也都被剪枝后不存在任何节点（即左右子节点都返回了 None），那么这个节点也应该被剪掉（返回 None）。递归首先处理左右子树，然后处理当前节点，这样可以保证从底部开始剪枝，只有当一个节点的所有子树都不包含值为 1 的节点时，这个节点才会被剪掉。
时间复杂度: O(n)
空间复杂度: O(n)
# Definition for a binary tree node.
# 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: TreeNode) -> TreeNode:
if not root:
return None # 如果节点为空，直接返回None
root.left = self.pruneTree(root.left) # 递归剪枝左子树
root.right = self.pruneTree(root.right) # 递归剪枝右子树
if not root.left and not root.right and root.val == 0:
return None # 如果当前节点的值为0且左右子树都被剪枝（都是None），则剪掉当前节点
return root # 返回处理后的当前节点
这种处理方式不会遗漏任何应被剪枝的情况。这是因为按照题目的要求，只有当节点的值为0且其左右子树都不存在或者也是值为0且被剪枝的时候，这个节点才应当被剪枝。递归函数先处理子节点确保了在决定是否剪掉当前节点前，其子树已经根据同样的规则被处理。因此，如果一个节点及其所有子节点的值都为0，它们都将在递归过程中被正确地剪枝。
递归剪枝的顺序（先左后右，然后当前节点）对最终结果并没有影响，因为剪枝的决定基于节点值及其子节点的状态，这需要子节点先被处理。如果先处理当前节点再递归子树，将无法正确实现剪枝逻辑。因为剪枝决定依赖于子节点的状态，如果未先递归处理子节点，就无法知道子节点是否应该被剪枝，从而不能决定当前节点是否应剪枝。因此，正确的处理顺序是关键。
是的，递归处理可能因为递归层次过深导致栈溢出，尤其是在处理非常深或不平衡的树时。一个非递归的替代方案是使用迭代方法结合栈或队列。例如，可以使用后序遍历的迭代版本来模拟递归的行为，先处理子节点然后处理父节点，使用栈来显式管理节点而不是依赖调用栈。这种方法需要更多的程序控制逻辑，但可以避免栈溢出的风险。