面试算法47:二叉树剪枝

这篇具有很好参考价值的文章主要介绍了面试算法47:二叉树剪枝。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

一棵二叉树的所有节点的值要么是0要么是1,请剪除该二叉树中所有节点的值全都是0的子树。例如,在剪除图8.2(a)中二叉树中所有节点值都为0的子树之后的结果如图8.2(b)所示。
面试算法47:二叉树剪枝,算法,算法,面试,剪枝

分析

下面总结什么样的节点可以被删除。首先,这个节点的值应该是0。其次,如果它有子树,那么它的子树的所有节点的值都为0。也就是说,如果一个节点可以被删除,那么它的子树的所有节点都可以被删除。

由此发现,后序遍历最适合用来解决这个问题。如果用后序遍历的顺序遍历到某个节点,那么它的左右子树的节点一定已经遍历过了。每遍历到一个节点,就要确定它是否有左右子树,如果左右子树都是空的,并且节点的值是0,那么也就可以删除这个节点。文章来源地址https://www.toymoban.com/news/detail-736303.html

public class Test {
    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node0 = new TreeNode(0);
        TreeNode node00 = new TreeNode(00);
        TreeNode node000 = new TreeNode(000);
        TreeNode node0000 = new TreeNode(0000);
        TreeNode node00000 = new TreeNode(00000);
        TreeNode node11 = new TreeNode(1);

        node1.left = node0;
        node1.right = node00;
        node0.left = node000;
        node0.right = node0000;
        node00.left = node00000;
        node00.right = node11;

        TreeNode result = pruneTree(node1);
        System.out.println(result);
    }

    public static TreeNode pruneTree(TreeNode root) {
        if (root == null) {
            return root;
        }

        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }

        return root;
    }
}

到了这里,关于面试算法47:二叉树剪枝的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 面试算法43:在完全二叉树中添加节点

    在完全二叉树中,除最后一层之外其他层的节点都是满的(第n层有2 n-1 个节点)。最后一层的节点可能不满,该层所有的节点尽可能向左边靠拢。例如,图7.3中的4棵二叉树均为完全二叉树。实现数据结构CBTInserter有如下3种方法。 构造函数CBTInserter(TreeNode root),用一棵完全

    2024年02月06日
    浏览(39)
  • 面试回忆录:链表&&二叉树

            链表与二叉树都是非常基础且非常重要的数据结构,这类题目在找工作面试中是非常高频的考题,非常考验基本功。作者在曾经在面试过程中,被要求现场写过的两道题目,分别是关于二叉树和链表的,因此对这两道题目记忆比较深刻。所以写下这篇博客与读者分享。 Lee

    2024年02月02日
    浏览(62)
  • 【数据结构】二叉树面试题

    目录 1.二叉树的最大深度 2.相同的树 3.另一棵树的子树 4.翻转二叉树 5.平衡二叉树 6.对称二叉树 7.完全二叉树 8.二叉树遍历 9.层序遍历 10.根据中序和前序序列构造二叉树 11.根据中序和后序序列构造二叉树 12.二叉树的最近公共祖先 13.非递归前序遍历 14.非递归中序遍历 15.非递

    2024年02月11日
    浏览(41)
  • 剑指offer面试题6 重建二叉树

    分析 本题目输入的一个树的前序和中序遍历序列,要求把这颗树重建起来。这里需要了解到程序中有个特别重要的思维叫递归,递归是分层的,每一层的问题都是一样的,只不过问题的规模不一样,面对这类复杂问题你的思考方式一定是2点:1.问题该如何定义?第n层该如何

    2024年01月18日
    浏览(43)
  • 【数据结构】 二叉树面试题讲解->贰

    二叉树的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于二叉树的应用题目,马上要进行秋招了。希望对你们有帮助 _😀 编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序

    2024年02月10日
    浏览(44)
  • 【数据结构】 二叉树面试题讲解->壹

    二叉树的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于二叉树的应用题目,马上要进行秋招了。希望对你们有帮助 _😀 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同

    2024年02月10日
    浏览(49)
  • 【数据结构】 二叉树面试题讲解->叁

    二叉树的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于二叉树的应用题目,马上要进行秋招了。希望对你们有帮助 _😀 给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字

    2024年02月09日
    浏览(33)
  • 一套模板搞定二叉树算法题--二叉树算法讲解002

    递归: 每个节点 都要恰好被访问一次, 本质上是二叉树的线性化 。 一个树形的结构,线性化为一个数组之类的\\\"串\\\"的结构。 示例二叉树原型图: 前序遍历执行顺序: 根节点--对左子树做前序遍历--对右子树做前序遍历 总的顺序:根节点--左子树--右子树 左子树中:根-左

    2024年02月02日
    浏览(36)
  • 一套模板搞定二叉树算法题--二叉树算法讲解004

    模拟忘记知识点和技巧时,遇到一个新的二叉树习题,该如何处理思考和写代码解题? 题目和题意: 题解1 成员变量self.ans: 题解2 递归回传: 该题是个经典二叉树题目 题目和题意: 题解: 分析,所有路径,每一个叶子节点都需要到达。到达之后,需要退出回到上一层的叶

    2024年02月19日
    浏览(36)
  • 一套模板搞定二叉树算法题--二叉树算法讲解003

    题目和题意: 图示: 题解: 题目和题意: 题解: 题目和题意: 题解: 题目和题意: 题解1: 写法1: 写法2: 题解2: 题目和题意: 题解:该题与叶子节点强相关,和自顶向下或自底向上并不强相关。 自底向上的图示: 题目和题意: 题解: 简洁写法: 思路易理解,代码

    2024年02月19日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包