(每日一道算法题)二叉树剪枝

814. 二叉树剪枝 - 力扣（LeetCode）

算法思路：深度优先的后序遍历

​​核心逻辑​​：自底向上检查每棵子树，只有全零叶子节点才被移除。

​​后序遍历顺序​​：先递归处理左右子树，再判断当前节点

• 确保子树已被修剪，当前节点基于最新子树状态决策

​​删除条件​​：仅当节点同时满足

• 节点值为 0
• 无左子树（left == null）
• 无右子树（right == null)
  时才被移除（返回 null 断开父节点引用）

​​为何这样设计？​​

• 非叶子节点即使值为 0，只要连接有效子树（含 1）就不能删除（如示例1的 0 节点）
• 后序遍历保证从叶子向上处理，避免重复判断

代码实现 

class Solution {public TreeNode pruneTree(TreeNode root) {if (root == null) return null;// 先递归处理子树root.left = pruneTree(root.left);root.right = pruneTree(root.right);// 当且仅当是叶子节点且值为0时移除if (root.val == 0 && root.left == null && root.right == null) {return null;}return root;}
}

示例推演 

原始树：        递归后：        返回结果：1            1              1\            \              \0    →       0     →         0/ \             \               \0   1             1               1

1. 递归到左叶节点 0​​：
   满足 val=0 且无子树 → 返回 null（移除）
   → 父节点 0 的左子树置为 null
2. ​​处理父节点 0​​：
   值 0 但右子树含 1 → 保留
3. ​​根节点 1​​：
   值 1 直接保留，最终形成新结构

关键步骤解析

​​深度递归​​
root.left = pruneTree(root.left) 先深入到左子树底部
root.right = pruneTree(root.right) 再深入到右子树底部
（形成自底向上的处理链）

​​精准剪枝​​
if (root.val == 0 && root.left == null && root.right == null)
仅当当前节点是值为 0 的叶子节点时才移除，保留两种情况：

• 值为 1 的节点（无论是否叶子）
• 值为 0 但连接有效子树的中间节点

​​时间复杂度​​

• O(n)：每个节点仅访问一次（n 为节点数）
• 空间复杂度 O(h)：递归栈深度（h 为树高，最坏 O(n)）

总结

通过​​后序遍历+叶子节点精准判断​​实现高效剪枝：

• 适用场景：树型数据处理中移除无效分支（如零值配置、空目录清理）
• 扩展思考：若修改为"保留至少含一个 1 的子树"，代码逻辑不变（本解法已实现）
• 工程启示：递归深度优先搜索是处理树型结构的利器，以 O(n) 时间完成复杂裁剪