LeetCode刷题--- 二叉树剪枝

2023-12-13 07:05:46

个人主页元清加油_【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节点),删除这棵二叉树所有不包含1(val != 1)的节点

例如:


算法原理思路讲解???

如果我们选择从上往下删除,我们需要收集左右?树的信息,这可能导致代码编写相对困难。
如下图所示,我们若想删除标红的节点,我们需要收集左右?树的信息
如果我们先删除最底部的叶?节点,然后再处理删除后的节点,操作起来比较简单
如下图所示,我们若想删除标红的节点,直接删除即可
因此,我们可以采?后序遍历的?式来解决这个问题
  1. 我们先处理左?树,然后处理右?树,最后再处理当前节点。
  2. 在处理当前节点时,我们可以判断其是否为叶?节点且其值是否为 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;
        
    }
};

文章来源:https://blog.csdn.net/weixin_74268082/article/details/134954925
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。