二叉树剪枝 -LeetCode

814. 二叉树剪枝 - Binary Tree Pruning

🎯 问题描述（来源于LeetCode）

描述：
给定一棵二叉树的根节点 root，树的每个节点值都是 0 或 1。
要求剪去所有不包含 1 的子树（即子树中所有节点值均为 0），并返回结果树的根节点。

说明：

• 剪枝后，原树中所有不含 1 的子树都应被删除。
• 被删除的子树应包括该子树的所有节点。
• 如果整棵树不含 1，则返回空。

示例：

• 示例 1：

输入: root = [1,null,0,0,1]
输出: [1,null,0,null,1]
解释: 最底层的左叶子 0 被删除（其子树和为 0），右子树中的 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：后序遍历 + 假根节点

算法步骤

1. 定义递归函数 dfs(node)：

   • 返回以 node 为根的子树中所有节点值之和。
   • 递归终止：若 node 为 None，返回 0。
   • 先递归计算左子树和与右子树和：left_sum = dfs(node.left)，right_sum = dfs(node.right)。
   • 如果左子树和为 0，则删除左子树：node.left = None。
   • 如果右子树和为 0，则删除右子树：node.right = None。
   • 返回当前子树的节点值和：node.val + left_sum + right_sum。

2. 处理根节点可能被剪枝：

   • 创建一个值为 1 的假根节点 new_root，其左孩子指向原树 root。
   • 调用 dfs(new_root)，递归删除所有和为 0 的子树。
   • 返回 new_root.left（剪枝后的真正根节点）。

思路1：代码实现

class Solution:
    def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return 0
            left_sum = dfs(node.left)
            right_sum = dfs(node.right)
            if left_sum == 0:
                node.left = None
            if right_sum == 0:
                node.right = None
            return node.val + left_sum + right_sum
        
        new_root = TreeNode(1, root)
        dfs(new_root)
        return new_root.left

思路1：📊 性能分析

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：$O(h)$，递归栈深度为树高。

---

思路2：后序遍历 + 直接剪枝（无需假根）

算法步骤

1. 递归函数 pruneTree(root)：

   • 如果 root 为空，直接返回 None。
   • 先递归处理左子树：root.left = self.pruneTree(root.left)
   • 再递归处理右子树：root.right = self.pruneTree(root.right)
   • 剪枝条件判断：如果当前节点值为 0，且左右子树均为空（即已被剪掉），则当前节点应当被删除，返回 None。
   • 否则返回当前节点 root。

2. 主函数直接调用：

   • 从根节点开始递归，最终返回的 root 即为剪枝后的树根（可能为 None）。

思路2：代码实现

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 not root.left and not root.right:
            return None
        return root

思路2：📊 性能分析

• 时间复杂度：$O(n)$，每个节点访问一次。
• 空间复杂度：$O(h)$，递归栈深度为树高。

思考

• 思路1 通过额外假根节点统一处理根节点删除，代码稍显冗余但逻辑清晰。
• 思路2 更简洁，完全利用递归返回 None 来删除节点，是本题的标准解法。
• 两种思路均基于后序遍历：先处理子节点，再决定父节点是否保留。
• 注意：剪枝后，原来值为 0 但左右子树有 1 的节点必须保留（因为子树包含 1，不能整体删除）。