本次刷题日记的第 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. 二叉树剪枝
今天就到这里，学习所得，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
