LeetCode每日一题——814. 二叉树剪枝

简介: 给你二叉树的根结点 root ,此外树的每个结点的值要么是 0 ,要么是 1 。

题目

给你二叉树的根结点 root ,此外树的每个结点的值要么是 0 ,要么是 1 。

返回移除了所有不包含 1 的子树的原二叉树。

节点 node 的子树为 node 本身加上所有 node 的后代。

示例

示例 1:

2345_image_file_copy_30.jpg

输入:root = [1,null,0,0,1]

输出:[1,null,0,null,1]

解释: 只有红色节点满足条件“所有不包含 1的子树”。 右图为返回的答案。

示例 2:

2345_image_file_copy_31.jpg

输入:root = [1,0,1,0,0,0,1]

输出:[1,null,1,null,1]

示例 3:

2345_image_file_copy_32.jpg

输入:root = [1,1,0,1,1,0,1,0]

输出:[1,1,0,1,1,null,1]

提示:

树中节点的数目在范围 [1, 200] 内

Node.val 为 0 或 1

题目

  • 首先明确要删除节点的特征
    1、从下往上删除
    2、为叶子节点
    3、节点值为0
  • dfs重新构造树,判断是否为叶子节点且值为零,如果是将该节点置空,不是则跳过。

题解

class Solution:
    # dfs遍历
    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 not root.left and not root.right and root.val == 0:
            return None
        return root
目录
相关文章
|
2月前
|
决策智能
【LeetCode 50】77.组合(优化、剪枝操作)
【LeetCode 50】77.组合(优化、剪枝操作)
16 2
|
2月前
【LeetCode 31】104.二叉树的最大深度
【LeetCode 31】104.二叉树的最大深度
20 2
|
2月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
18 2
|
2月前
【LeetCode 28】102.二叉树的层序遍历
【LeetCode 28】102.二叉树的层序遍历
16 2
|
2月前
【LeetCode 43】236.二叉树的最近公共祖先
【LeetCode 43】236.二叉树的最近公共祖先
20 0
|
2月前
【LeetCode 38】617.合并二叉树
【LeetCode 38】617.合并二叉树
15 0
|
2月前
【LeetCode 37】106.从中序与后序遍历构造二叉树
【LeetCode 37】106.从中序与后序遍历构造二叉树
17 0
|
2月前
【LeetCode 34】257.二叉树的所有路径
【LeetCode 34】257.二叉树的所有路径
20 0
|
2月前
【LeetCode 32】111.二叉树的最小深度
【LeetCode 32】111.二叉树的最小深度
19 0
|
4月前
|
存储 算法
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题
文章深入探讨了二叉树的层序遍历方法,并展示了如何通过队列实现层序遍历的算法逻辑,同时指出掌握层序遍历技巧可以帮助解决LeetCode上的多道相关题目。
二叉树进阶-学会层序遍历助你一次刷完leetcode10道题