当前位置：首页 > web >正文

8.二叉树减枝

web 2025/5/15 4:19:19

1.题目链接：

814. 二叉树剪枝 - 力扣（LeetCode）814. 二叉树剪枝 - 给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。返回移除了所有不包含 1 的子树的原二叉树。节点 node 的子树为 node 本身加上所有 node 的后代。示例 1：[https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_2.png]输入：root = [1,null,0,0,1]输出：[1,null,0,null,1]解释：只有红色节点满足条件“所有不包含 1 的子树”。右图为返回的答案。示例 2：[https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/06/1028_1.png]输入：root = [1,0,1,0,0,0,1]输出：[1,null,1,null,1]示例 3：[https://s3-lc-upload.s3.amazonaws.com/uploads/2018/04/05/1028.png]输入：root = [1,1,0,1,1,0,1,0]输出：[1,1,0,1,1,null,1] 提示： * 树中节点的数目在范围 [1, 200] 内 * Node.val 为 0 或 1https://leetcode.cn/problems/binary-tree-pruning/description/

2.题目描述：

给你二叉树的根结点 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. 解法（dfs - 后序遍历）：

后序遍历按照左子树、右子树、根节点的顺序遍历二叉树的所有节点，通常用于父节点的状态依赖于子节点状态的题目。

算法思路：

如果我们选择从上往下删除，我们需要收集左右子树的信息，这可能导致代码编写相对困难。然而，通过观察我们可以发现，如果我们先删除最底部的叶子节点，然后再处理删除后的节点，最终的结果并不会受到影响。

因此，我们可以采用后序遍历的方式来解决这个问题。在后序遍历中，我们先处理左子树，然后处理右子树，最后再处理当前节点。在处理当前节点时，我们可以判断其是否为叶子节点且其值是否为 0，如果满足条件，我们可以删除当前节点。

•需要注意的是，在删除叶子节点时，其父节点很可能会成为新的叶子节点。因此，在处理完子节点后，我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因（后序遍历首先遍历到的一定是叶子节点）。

•通过使用后序遍历，我们可以逐步删除叶子节点，并且保证删除后的节点仍然满足删除操作的要求。这样，我们可以较为方便地实现删除操作，而不会影响最终的结果。

•若在处理结束后所有叶子节点的值均为 1，则所有子树均包含 1，此时可以返回。

算法流程：

递归函数设计：void dfs(TreeNode*& root)

1. 返回值：无；

2. 参数：当前需要处理的节点；

3. 函数作用：判断当前节点是否需要删除，若需要删除，则删除当前节点。

后序遍历的主要流程：

1. 递归出口：当传入节点为空时，不做任何处理；
2. 递归处理左子树；
3. 递归处理右子树；
4. 处理当前节点：判断该节点是否为叶子节点（即左右子节点均被删除，当前节点成为叶子节点），并且节点的值为 0：
a. 如果是，就删除掉；
b. 如果不是，就不做任何处理。

Java算法代码：

class Solution {public TreeNode pruneTree(TreeNode root) {if(root == null) return null;root.left = pruneTree(root.left);root.right = pruneTree(root.right);return (root.left == null && root.right ==null && root.val == 0)? null : root;}
}

结果：