测试岗位也越来卷了，除了基本的功能测试外，还要有编程基础、脚本经验才脱颖而出。

怎么才能提高我们的编程能力呢，刷LeetCode是最佳的途径之一，话不多数,刷题走起~

一、题目描述：

• 题目内容

• 题目示例

• 题目解析

  • 树中节点的数目在范围 [1, 200] 内
  • Node.val 为 0 或 1

二、思路分析：

我们拿到本题，要求对二叉树中对所有不包含1的子树做移除处理，得到一个剪枝过的新树。那什么是不包含1的子树，我们带的疑问继续从题目中获取信息。

• 二叉树root的所有节点的val只有两种形式：1和0
• 不包含1的子树计算方式是：包含node本身值和其所有后代的总和

通过题目示例2，我们来画图演示下二叉树剪枝过程：

审完题目查看示例，我们对二叉树剪枝过程大致了解了，因此解答本题我们使用模拟方法即可。

众所周知，二叉树遍历有两种方式：广度优先遍历bfs和深度优先遍历dfs

在本题中，我们需要知道node节点的所有后代，因此采用深度优先遍历最为方便。

应用在本题，我们解题思路如下：

• 对剪枝过程进行拆解分为：node.val 为零、node的左子树为空 和node的右子树为空时，则进行移除这棵树，返回None
• 使用深度优先遍历-后序遍历递归方法，当root为空时，则直接返回None
• 继续判断使用pruneTree(root.left)和pruneTree(root.right)子树
• 当不符合剪枝条件，则返回当前节点

根据以上思路，我们使用Python实现，代码如下：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def pruneTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        if root is None:return None
        root.left = self.pruneTree(root.left)
        root.right = self.pruneTree(root.right)
        if root.right is None and root.left is None and root.val == 0:
            return None      
        return root

三、总结：

本题考察我们对二叉树深度遍历的理解，已经对剪枝条件归纳，当node值为0并且左子树和右子树都为空时，则对该子树进行移除返回None，否则不满足剪枝要求。

• 时间复杂度：O(n),n为二叉树的节点数
• 空间复杂度：O(n),n为二叉树的深度

以上是本期内容，欢迎大佬们点赞评论，下期见~~