专栏首页小浩算法二叉树剪枝了解一下~

二叉树剪枝了解一下~

在之前的系列中。我们学习了DFS、BFS,也熟悉了平衡二叉树,满二叉树,完全二叉树,BST(二叉搜索树)等概念。在本节中,我们将学习一种二叉树中常用的操作 —剪枝。这里额外说一点,就本人而言,对这个操作以及其衍化形式的使用会比较频繁。因为我是做规则引擎的,在规则引擎中,我们会有一个概念叫做决策树,那如果一颗决策树完全生长,就会带来比较大的过拟合问题。因为完全生长的决策树,每个节点只会包含一个样本。所以我们就需要对决策树进行剪枝操作,来提升整个决策模型的泛化能力(ML概念)... 听不懂也没关系,简单点讲,就是我觉得这个很重要,或者每道算法题都很重要。如果你在工作中没有用到,不是说明算法不重要,而可能是你还不够重要。

01、剪枝概述

假设有一棵树,最上层的是root节点,而父节点会依赖子节点。如果现在有一些节点已经标记为无效,我们要删除这些无效节点。如果无效节点的依赖的节点还有效,那么不应该删除,如果无效节点和它的子节点都无效,则可以删除。剪掉这些节点的过程,称为剪枝,目的是用来处理二叉树模型中的依赖问题

我们还是通过一道题目来进行具体学习。

02、题目分析

第814题:二叉树的剪枝

给定二叉树根结点 root ,此外树的每个结点的值要么是 0,要么是 1。返回移除了所有不包含 1 的子树的原二叉树。( 节点 X 的子树为 X 本身,以及所有 X 的后代。)

示例1:

输入: [1,null,0,0,1]
输出: [1,null,0,null,1]

**解释: **

  • 只有红色节点满足条件“所有不包含 1 的子树”。
  • 右图为返回的答案。

示例2:

输入: [1,0,1,0,0,0,1]
输出: [1,null,1,null,1]

示例3:

输入: [1,1,0,1,1,0,1,0]
输出: [1,1,0,1,1,null,1]

说明:

  • 给定的二叉树最多有 100 个节点。
  • 每个节点的值只会为 0 或 1 。

03、递归求解

二叉树的问题,大多都可以通过递归进行求解。我们直接进行分析。假设我们有二叉树如下:[0,1,0,1,0,0,0,0,1,1,0,1,0]

就是下面这样:

剪枝之后是这样:

剪什么大家应该都能理解。那关键是怎么剪?过程也很简单,在递归的过程中,如果当前结点的左右节点皆为空,且当前结点为0,我们就将当前节点剪掉即可。

根据分析,很自然得出代码:

func pruneTree(root *TreeNode) *TreeNode {
 return deal(root)
}

func deal(node *TreeNode) *TreeNode {
 if node == nil {
  return nil
 }
 node.Left = deal(node.Left)
 node.Right = deal(node.Right)
 if node.Left == nil && node.Right == nil && node.Val == 0 {
  return nil
 }
 return node
}

运行结果:

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode - 二叉树剪枝

    原题地址:https://leetcode-cn.com/problems/binary-tree-pruning/

    晓痴
  • LeetCode 814. 二叉树剪枝(递归)

    Michael阿明
  • 基础扫盲:二叉树系列 第三讲(二叉树的剪枝)

    在之前的系列中。我们学习了DFS、BFS,也熟悉了平衡二叉树,满二叉树,完全二叉树,BST(二叉搜索树)等概念。在本节中,我们将学习一种二叉树中常用的操作 --...

    帅地
  • 漫画:二叉树系列 第八讲(二叉树的剪枝)

    在之前的系列中。我们学习了DFS、BFS,也熟悉了平衡二叉树,满二叉树,完全二叉树,BST(二叉搜索树)等概念。在本节中,我们将学习一种二叉树中常用的操作 --...

    程序员小浩
  • 机器学习17:决策树模型

    决策树分为两大类:分类树和回归树,分类树用于分类标签值,回归树用于预测连续值,常用算法有ID3、C4.5、CART等。

    用户5473628
  • 决策树学习笔记(三):CART算法,决策树总结

    推荐导读:本篇为树模型系列第三篇,旨在从最简单的决策树开始学习,循序渐进,最后理解并掌握复杂模型GBDT,Xgboost,为要想要深入了解机器学习算法和参加数据...

    1480
  • 决策树学习笔记(三):CART算法,决策树总结

    推荐导读:本篇为树模型系列第三篇,旨在从最简单的决策树开始学习,循序渐进,最后理解并掌握复杂模型GBDT,Xgboost,为要想要深入了解机器学习算法和参加数据...

    Python数据科学
  • 机器学习(12)之决策树总结与python实践(~附源码链接~)

    关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 前言 在(机器学习(9)之ID3算法...

    昱良
  • 从全排列看回溯算法

    最近又刷起了算法,仿佛回到了大一时奋战到深夜场景,走上社会之初发现大学里学的都是啥玩意儿,工作中基本遇不到,各种数据结构都被封装的妥妥的根本不需要...

    sealyun

扫码关注云+社区

领取腾讯云代金券