【leetcode-Python】-Tree-814. Binary Tree Pruning

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【leetcode-Python】-Tree-814. Binary Tree Pruning，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2305字，纯文字阅读大概需要4分钟。

内容图文

题目链接

https://leetcode.com/problems/binary-tree-pruning/solution/

题目描述 

给定一棵二叉树，树中每个节点的值要么为0，要么为1。从原二叉树中移除所有不包含1的子树后返回结果。

示例

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

输出：[1,null,1,null,1]

 解决思路

第一种方法是递归。递归函数的作用是判断以root为根节点的子树中是否含有1，如果没有1进行剪枝并返回False，如果含有1则返回True。递归结束条件是传入的节点root为空（递归到叶子节点的下一层），此时返回False。在问题拆解中，判断当前以root为根节点的子树是否含有1被拆解为（root的值是否为1）&& （以root.left为根节点的子树是否含1）&& (以root.right为根节点的子树是否含1)。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isContainsOne(self,root):#判断以root为根节点的子树是否含有1，如果没有则进行剪枝
        if not root:#要考虑到叶子节点可能会传入其为None的子节点
            return False
        is_left_contains_one = self.isContainsOne(root.left)#判断左子树是否有1
        is_right_contains_one = self.isContainsOne(root.right)#判断右子树是否有1
        if not is_left_contains_one:#剪枝
            root.left = None
        if not is_right_contains_one:
            root.right = None 
        return root.val or is_left_contains_one or is_right_contains_one
    def pruneTree(self, root: TreeNode) -> TreeNode:
        return root if self.isContainsOne(root) else None

另一种递归函数的设计更直接： 递归函数的任务是返回以root为根节点的子树剪枝后的结果（返回剪枝后树的根节点）。递归结束条件为root为空。

对以root为根节点的剪枝包括对root左子树的剪枝和对root右子树的剪枝以及对root.val的判断】=果root左子树剪枝结果返回None（即root的左子树没有1）且右子树剪枝结果返回None（root的右子树）且root的值为0，那么说明以root为根节点的子树不含1，应当被修剪，因此应该返回None。代码如下：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if not root.left and not root.right and not root.val:
            return None
        return root
    
        

时间复杂度和空间复杂度

时间复杂度为O(n), 因为每个节点仅被访问一次。空间复杂度为O(H),H为树的高度，需要构建大小为H的栈用于递归。
 

内容总结

以上是互联网集市为您收集整理的【leetcode-Python】-Tree-814. Binary Tree Pruning全部内容，希望文章能够帮你解决【leetcode-Python】-Tree-814. Binary Tree Pruning所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端