我是靠谱客的博主 开放铃铛,这篇文章主要介绍222. 完全二叉树的节点个数,现在分享给大家,希望可以做个参考。

在这里插入图片描述
首先需要明确完全二叉树的定义:它是一棵空树或者它的叶子节点只出在最后两层,若最后一层不满则叶子节点只在最左侧。

再来回顾一下满二叉的节点个数怎么计算,如果满二叉树的层数为h,则总节点数为:2^h - 1.
那么我们来对 root 节点的左右子树进行高度统计,分别记为 left 和 right,有以下两种结果:

left == right。这说明,左子树一定是满二叉树,因为节点已经填充到右子树了,左子树必定已经填满了。所以左子树的节点总数我们可以直接得到,是 2^left - 1,加上当前这个 root 节点,则正好是 2^left。再对右子树进行递归统计。
left != right。说明此时最后一层不满,但倒数第二层已经满了,可以直接得到右子树的节点个数。同理,右子树节点 +root 节点,总数为 2^right。再对左子树进行递归查找。
关于如何计算二叉树的层数,可以利用下面的递归来算,当然对于完全二叉树,可以利用其特点,不用递归直接算,具体请参考最后的完整代码。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution { public int countNodes(TreeNode root) { if(root == null){ return 0; } int left = countLevel(root.left); int right = countLevel(root.right); if(left == right){ return countNodes(root.right) + (1<<left); }else{ return countNodes(root.left) + (1<<right); } } private int countLevel(TreeNode root){ int level = 0; while(root != null){ level++; root = root.left; } return level; }

最后

以上就是开放铃铛最近收集整理的关于222. 完全二叉树的节点个数的全部内容,更多相关222.内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(71)

评论列表共有 0 条评论

立即
投稿
返回
顶部