栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

【算法hot】完全二叉树的节点个数

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【算法hot】完全二叉树的节点个数

完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ,求出该树的节点个数。

完全二叉树 的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2h 个节点。

public class LC274_222_countNodes_01 {
    public static void main(String[] args) {
        TreeNode root = TreeNode.generateRandomBST(1, 100, 3);
        TreeNode.printTree(root);
        System.out.println(countNodes(root));
    }

    //层序遍历
    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}
public class LC274_222_countNodes_02 {

    public static void main(String[] args) {
        System.out.println(countNodes(TreeNode.generateRandomBST(1, 100, 5)));
    }

    //层序遍历
    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int ans = 0;
        Queue queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode pop = queue.poll();
            if (pop.left != null) {
                queue.offer(pop.left);
            }
            if (pop.right != null) {
                queue.offer(pop.right);
            }
            ans++;
        }
        return ans;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/986498.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号