当前位置:首页 » 《随便一记》 » 正文

LeetCode 814. 二叉树剪枝_数据结构和算法

22 人参与  2021年11月18日 16:03  分类 : 《随便一记》  评论

点击全文阅读


截止到目前我已经写了 600多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

在这里插入图片描述
在这里插入图片描述

这题是说如果二叉树的任一节点的左子树都是0,就把他的左子树删除,同理如果右子树都是0,也把他的右子树给删除。


这题常规思路是从根节点开始统计他的左右子树节点是否都是0,如果任一子树的所有节点都是0,就把他给删除。否则不能删除,然后再统计不能删除节点的子节点……,那这样的话工作量就非常大,并且还会出现大量重复计算,如下图所示:

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
上面方式明显是行不通的。我们可以这样来思考一下,从上到下删不行,那么从下到上呢,如果是叶子节点并且值为0,我们就把他给删除,否则不要删除,看下视频,视频链接
在这里插入图片描述
看到这里大家可能就明白了,这就是二叉树的后续遍历,我们来看下代码

public TreeNode pruneTree(TreeNode root) {
    if (root == null)
        return null;
    //这里要注意,当前节点可能不是叶子节点,但如果他的子节点
    //都删除完了,它就变成了叶子节点。
    //剪枝左子树
    root.left = pruneTree(root.left);
    //剪枝右子树
    root.right = pruneTree(root.right);
    //如果叶子节点的值是0,就把他给删除,返回一个空的节点
    if (root.left == null && root.right == null && root.val == 0)
        return null;
    //否则不要删除,直接返回即可
    return root;
}

时间复杂度O(n)n是二叉树中节点的个数。
空间复杂度O(h)h是树的高度,也是递归的深度。


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/31011.html

子树  节点  删除  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • (此去经年无故人)南初陆南城:结局+番外精品选集起点章节+阅读即将发布预订
  • 沈凝夏叶晚怡附加完整在线阅读(归雁不栖故人枝)最近更新列表
  • 剧情人物是时初,白浩雄的玄幻言情小说《召诸神,踏万界,天命帝女逆乾坤》,由网络作家&ldquo;海鸥&rdquo;所著,情节扣人心弦,本站TXT全本,欢迎阅读!本书共计381345字,185章节,:结局+番外免费品鉴:结局+番外评价五颗星
  • 凤青禾,江明远,***枢小说(别人修仙我捡漏,卷王们破防了)最近更新(凤青禾,江明远,***枢)整本无套路阅读
  • 薛梨小说无删减+后续(曾经亲情似草芥)畅享阅读
  • 沈南栀小说(穿越时空,我要修补时空裂缝)章节目录+起点章节(沈南栀)全篇清爽版在线
  • 未婚妻被巨蟒缠身,我该吃就吃该喝就喝前言+后续_阿豪林月周然后续+番外_小说后续在线阅读_无删减免费完结_
  • 陆骁,陆本初小说(陆骁,陆本初)(癫!睁眼穿成老太太挥鞭***逆子)前传+阅读全新作品预订
  • 姐姐含冤而死后冥王另娶,我杀穿整个地府在线阅读_阎罗殿殷红别提一口气完结_小说后续在线阅读_无删减免费完结_
  • (书荒必看)毒后重生:疯王的神医小娇妻沈清歌,萧绝:+后续热血十足
  • 重生后我和太监联手灭了敌国喻辰,林雪续集(重生后我和太监联手灭了敌国)终极反转(喻辰,林雪)全篇一口气阅读
  • 我不做灵媒后,自称灵媒摆渡人的养妹害怕了内容精选_苏晓霍老阿姐无广告_小说后续在线阅读_无删减免费完结_

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1