使用flask做前后端分离的网站,wordpress 导入html,做网站优化排名,怎么申请建立个人免费网站文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;二叉树剪枝
出处#xff1a;814. 二叉树剪枝
难度
4 级
题目描述
要求
给定二叉树的根结点 root \texttt{root} root#xff0c;返回移除了所有… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题二叉树剪枝
出处814. 二叉树剪枝
难度
4 级
题目描述
要求
给定二叉树的根结点 root \texttt{root} root返回移除了所有不包含 1 \texttt{1} 1 的子树的原二叉树。
结点 node \texttt{node} node 的子树为 node \texttt{node} node 本身以及所有 node \texttt{node} node 的后代。
示例
示例 1 输入 root [1,null,0,0,1] \texttt{root [1,null,0,0,1]} root [1,null,0,0,1] 输出 [1,null,0,null,1] \texttt{[1,null,0,null,1]} [1,null,0,null,1] 解释 只有红色结点满足条件「所有不包含 1 \texttt{1} 1 的子树」。右图为返回的答案。
示例 2 输入 root [1,0,1,0,0,0,1] \texttt{root [1,0,1,0,0,0,1]} root [1,0,1,0,0,0,1] 输出 [1,null,1,null,1] \texttt{[1,null,1,null,1]} [1,null,1,null,1]
示例 3 输入 root [1,1,0,1,1,0,1,0] \texttt{root [1,1,0,1,1,0,1,0]} root [1,1,0,1,1,0,1,0] 输出 [1,1,0,1,1,null,1] \texttt{[1,1,0,1,1,null,1]} [1,1,0,1,1,null,1]
数据范围
树中结点数目在范围 [1, 200] \texttt{[1, 200]} [1, 200] 内 Node.val \texttt{Node.val} Node.val 是 0 \texttt{0} 0 或 1 \texttt{1} 1
解法
思路和算法
如果二叉树为空则不需要执行剪枝操作直接返回即可。
当二叉树不为空时需要首先对二叉树的左子树和右子树执行剪枝操作然后对当前二叉树执行剪枝操作。剪枝操作具体为如果一个结点是叶结点且结点值为 0 0 0则该结点被移除。注意在移除值为 0 0 0 的叶结点之后被移除的结点的父结点可能从非叶结点变成叶结点。
由于每个结点是否需要被移除和结点的子树有关因此可以使用深度优先搜索实现。
整个过程是一个递归的过程。递归的终止条件是当前结点为空或者当前结点是叶结点且结点值为 0 0 0这两种情况都返回空二叉树。对于其余情况递归地对左子树和右子树执行剪枝操作。
由于剪枝操作只会移除所有的值为 0 0 0 的叶结点包括从非叶节点变成叶结点的值为 0 0 0 的结点不会移除值为 1 1 1 的结点因此剪枝操作可以确保移除所有不包含 1 1 1 的子树。
代码
class Solution {public TreeNode pruneTree(TreeNode root) {if (root null) {return root;}root.left pruneTree(root.left);root.right pruneTree(root.right);if (root.left null root.right null root.val 0) {root null;}return root;}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。每个结点都被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间取决于二叉树的高度最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。
