济南公司注册网站,徐州地产开发公司国企,网站发布内容是否过滤,文化传媒公司广告宣传文章目录 C二叉树剪枝题目链接题目描述解题思路代码复杂度分析 C二叉树剪枝
题目链接 LCR 047. 二叉树剪枝 - 力扣#xff08;LeetCode#xff09; 题目描述 给定一个二叉树 根节点 root #xff0c;树的每个节点的值要么是 0#xff0c;要么是 1。请剪除该二叉树中所有节… 文章目录 C二叉树剪枝题目链接题目描述解题思路代码复杂度分析 C二叉树剪枝
题目链接 LCR 047. 二叉树剪枝 - 力扣LeetCode 题目描述 给定一个二叉树 根节点 root 树的每个节点的值要么是 0要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。 节点 node 的子树为 node 本身以及所有 node 的后代。 解题思路 首先我们分为三步 ①函数头 首先我们应该想到我们去递归解答这道题目函数的参数非常好确认就是TreeNode* root即可。 函数的返回值根据题目的意思我们要将那些全零的子树全部在树中删除那么我们最好是返回一个TreeNode*即可。 ②函数体 我们要实现的肯定是一个深度优先遍历dfs,那么 1dfs(root-left); 2dfs(root-right); (3) 处理当前root ③截止条件 当我们深度历到root nullptr为空的时候 代码
class Solution {
public:TreeNode* pruneTree(TreeNode* root) {if(root nullptr)return nullptr;root-left pruneTree(root-left);root-right pruneTree(root-right);if(root-left nullptr root-right nullptr root-val 0)root nullptr;return root;}
}复杂度分析 时间复杂度 dfs时间复杂度为O(N); 空间复杂度 未使用额外的空间空间复杂度为O(1);
