【刷题日记】814. 二叉树剪枝

本次刷题日记的第 80 篇，力扣题为：814. 二叉树剪枝

一、题目描述：

今天来处理一个写一个二叉树剪枝的题目

二叉树剪枝，看上去感觉不是那么难，一起来撸一波

二、这道题考察了什么思想？你的思路是什么？

题目要求我们对二叉树进行剪枝，树的呈现方式是 根节点为 1，其余节点有 0 有 1，题目要求我们移除所有不包含 1 的子树

换句话说，就是要我们找到一个节点，它的左节点为空，右节点也为空，并且当前节点是 0 的情况，就将该节点移除

分析

上面有说到实际上我们就可以将问题转换成找那种左节点为空，右节点也为空，且自己的值是 0 的节点

那么如何将该节点移除呢？

此时遍历到这个节点的时候，就返回空就可以了，就相当于是移除了

根据这个逻辑，我们就是要先遍历当前节点的左节点，再遍历右节点，最后判断当前节点的值，显然是需要使用后序遍历的方式来进行处理

那么我们按照示例 2 的方式来进行推演一遍 ，看看咱们得出的结果几何

遍历方式是左右根，咱们先遍历左子树，当左子树遍历完毕之后，再遍历右子树，右子树遍历完毕之后，最后进行判断，对于每一个节点都是严格按照这个规则来进行处理

通过上图就能够很清晰的展示出，每一个节点的遍历情况，以及某些被移除节点的移除顺序

既然能够清晰的知道对于二叉树每一个节点的变动情况，那么对于我们编写代码来说就是一个简单翻译的过程的，有没有感觉很有趣？

三、编码

根据上述逻辑和分析，我们就可以翻译成如下代码

• 编写代码的时候，我们需要注意，如果给出的 root 节点就是空的话，那么我们就直接返回 nil 即可
• 我们采取的是后序遍历的方式，严格按照遍历规则来执行

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func pruneTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left = pruneTree(root.Left)
    root.Right = pruneTree(root.Right)
    if root.Left == nil && root.Right == nil && root.Val == 0 {
        return nil
    }
    return root
}

四、总结：

本题按照我们这种方式来进行处理，对于每一个节点都需要遍历到，因此对于时间复杂度是 O(n) ，

空间复杂度最多是 O(n)

原题地址：814. 二叉树剪枝

今天就到这里，学习所得，若有偏差，还请斧正

欢迎点赞，关注，收藏

朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力

好了，本次就到这里

技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。

我是阿兵云原生，欢迎点赞关注收藏，下次见~