网站建设黄页软件,设计品牌logo,公司logo设计用什么软件,wordpress如何转换为中文版个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏#xff1a;http://t.csdnimg.cn/ZxuNL http://t.csdnimg.cn/c9twt 前言#xff1a;这个专栏主要讲述递归递归、搜索与回溯算法#xff0c;所以下面题目主要也是这些算法做的
我讲述…个人主页元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏http://t.csdnimg.cn/ZxuNL http://t.csdnimg.cn/c9twt 前言这个专栏主要讲述递归递归、搜索与回溯算法所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分 1、题目解析
2、算法原理思路讲解
3、代码实现 二叉树剪枝题目
题目链接二叉树剪枝
题目
给你二叉树的根结点 root 此外树的每个结点的值要么是 0 要么是 1 。
返回移除了所有不包含 1 的子树的原二叉树。
节点 node 的子树为 node 本身加上所有 node 的后代。 示例 1 输入root [1,null,0,0,1]
输出[1,null,0,null,1]
解释
只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。示例 2 输入root [1,0,1,0,0,0,1]
输出[1,null,1,null,1]示例 3 输入root [1,1,0,1,1,0,1,0]
输出[1,1,0,1,1,null,1]提示
树中节点的数目在范围 [1, 200] 内Node.val 为 0 或 1 解法
题目解析
这道题目的意思很简单给我们一个二叉树的根节点root节点删除这棵二叉树所有不包含1val ! 1的节点。
例如 算法原理思路讲解 如果我们选择从上往下删除我们需要收集左右⼦树的信息这可能导致代码编写相对困难。 如下图所示我们若想删除标红的节点我们需要收集左右⼦树的信息 如果我们先删除最底部的叶⼦节点然后再处理删除后的节点操作起来比较简单 如下图所示我们若想删除标红的节点直接删除即可 因此我们可以采⽤后序遍历的⽅式来解决这个问题 我们先处理左⼦树然后处理右⼦树最后再处理当前节点。在处理当前节点时我们可以判断其是否为叶⼦节点且其值是否为 0 如果满⾜条件我们可以删除当前节点。
需要注意的是在删除叶⼦节点时其父节点很可能会成为新的叶⼦节点。因此在处理完⼦节点后我们仍然需要处理当前节点。这也是为什么选择后序遍历的原因后序遍历⾸先遍历到的⼀定是叶⼦节点通过使⽤后序遍历我们可以逐步删除叶⼦节点并且保证删除后的节点仍然满⾜删除操作的要求。这样我们可以较为⽅便地实现删除操作⽽不会影响最终的结果。 若在处理结束后所有叶⼦节点的值均为 1则所有⼦树均包含 1此时可以返回 1、设计函数头 TreeNode* dfs(TreeNode* root)
返回值根节点参数 当前需要处理的节点函数作⽤判断当前节点是否需要删除若需要删除则删除当前节点。
2、设计函数体和函数出口
进行后序遍历若遇到叶子节点并且val值为0那么删除该节点
if (root nullptr)return nullptr;root-left dfs(root-left);root-right dfs(root-right);if(root-left nullptr root-right nullptr root-val 0){delete root; // 防⽌内泄漏root nullptr;}return root;
以上思路就讲解完了大家可以先自己先做一下 时间复杂度O(n)其中 n 是二叉树节点的个数。每个节点都需要遍历一次。空间复杂度O(n)其中 n 是二叉树节点的个数。递归的深度最多为 O(n)。
代码实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
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){delete root; // 防⽌内泄漏root nullptr;}return root;}
};
