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

完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 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<TreeNode> 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;
    }
}

最后

以上就是冷酷绿草为你收集整理的【算法hot-222】完全二叉树的节点个数的全部内容，希望文章能够帮你解决【算法hot-222】完全二叉树的节点个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。