二叉树剪枝
难度:
标签:
题目描述
给你二叉树的根结点 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
代码结果
运行时间: 24 ms, 内存: 0.0 MB
/*
* 思路：
* 1. 使用 Java 8 Stream API 解决此问题。
* 2. 定义一个辅助方法 pruneTree，用于递归修剪树。
* 3. 在辅助方法中，递归处理左右子树。
* 4. 使用 Optional 类来处理节点的存在性。
*/
import java.util.Optional;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode pruneTree(TreeNode root) {
return Optional.ofNullable(root)
.map(node -> {
node.left = pruneTree(node.left);
node.right = pruneTree(node.right);
return (node.val == 0 && node.left == null && node.right == null) ? null : node;
})
.orElse(null);
}
}解释
方法:
这个解法使用了后序遍历的方式来剪枝二叉树。从叶子节点开始递归，如果一个节点的左右子树都被剪枝了，并且当前节点的值为0，那么当前节点也需要被剪枝。通过后序遍历，可以保证每个节点的子树都已经被正确剪枝后，再来判断当前节点是否需要剪枝。最后，如果整棵树都被剪枝了，就返回None，否则返回根节点。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
后序遍历为何是剪枝二叉树的合适选择？
▷🦆
在判断是否剪枝当前节点时，为什么即使左右子树都被剪枝，只要当前节点值为1，就不剪枝这个节点？
▷🦆
如果根节点的值为0且其左右子树也全被剪枝，这种情况下根节点是否被剪除，函数是否正确处理这种情况？
▷🦆
递归函数`subTreeFix`为什么在节点为None时返回False，这代表了什么意义？
▷