222. 完全二叉树的节点个数
1、概要
给出一个完全二叉树,求出该树的节点个数。
示例 1:
- 输入:root = [1,2,3,4,5,6]
- 输出:6
首先按照普通二叉树的逻辑来求。这道题目的递归法(后序)和求二叉树的深度(取MAX)写法类似, 而迭代法,遍历模板稍稍修改一下,记录遍历的节点数量就可以了
2、思路
普通二叉树
递归法
- 递归函数参数与返回值
private int reCurSion(TreeNode root)
- 终止条件
if(root == null){return 0;}
- 单层逻辑(累加)
return reCurSion(root.left)+reCurSion(root.right) + 1;
迭代法
加一个变量result,统计节点数量就可以了
在每层的for 增设result++,while循环退出后返回即可
完全二叉树性质
在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^(h-1) 个节点。
完全二叉树只有两种情况,情况一:就是满二叉树,情况二:最后一层叶子节点没有满。
-
情况一:可以直接用 2^树深度 - 1 来计算,注意这里根节点深度为1。
满二叉树(Full Binary Tree)是一种特殊的二叉树,其中每个节点要么是叶节点(没有子节点),要么有两个子节点。给定满二叉树的高度为h,其节点数量可以用以下公式计算:
节点数量 = 2^(h+1) - 1
这个公式可以这样理解:
- 在高度为0时(只有一个根节点),节点数量为1,符合公式2^(0+1) - 1 = 1。
- 每增加一层高度,节点数量翻倍。例如,高度为1时,节点数量为2;高度为2时,节点数量为4;高度为3时,节点数量为8,以此类推。
- 由于满二叉树的特性,每一层的节点数量都是最大可能的,因此总节点数量等于每一层节点数量的总和。通过等比数列求和公式,我们可以得到上述的节点数量公式。
请注意,这个公式仅适用于满二叉树。对于非满二叉树(如完全二叉树、平衡二叉树等),节点数量的计算方式会有所不同。
-
情况二:分别递归左孩子,和右孩子,递归到某一深度一定会有左孩子或者右孩子为满二叉树,然后依然可以按照情况1来计算。
如果整个树不是满二叉树,就递归其左右孩子,直到遇到满二叉树为止,用公式计算这个子树(满二叉树)的节点数量。
在完全二叉树中,如果递归向左遍历的深度等于递归向右遍历的深度,那说明就是满二叉树。不等于则不是满
3、代码
class Solution {
public int countNodes(TreeNode root) {
//return reCurSion(root);
//return iTeRation(root);
return comPleteBinaryTree(root);
}
private int reCurSion(TreeNode root){
if(root == null){return 0;}
return reCurSion(root.left)+reCurSion(root.right) + 1;
}
private int iTeRation(TreeNode root){
if(root == null){return 0;}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
int res = 0;
while(!que.isEmpty()){
int deep = que.size();
for(int i = 0;i<deep;i++){
TreeNode cur = que.poll();
res++;
if(cur.left!=null){que.offer(cur.left);}
if(cur.right!=null){que.offer(cur.right);}
}
}
return res;
}
private int comPleteBinaryTree(TreeNode root){
if(root==null){return 0;}
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0,rightDepth=0;
while(left!=null){
left = left.left;
leftDepth++;
}
while(right!=null){
right = right.right;
rightDepth++;
}
//完全二叉树,一定会有左孩子或者右孩子,为满二叉树,可以用公式 2^树深度-1计算
//左深度等于右深度 ,则说明是满二叉树
if(leftDepth == rightDepth){
return (int)Math.pow(2,leftDepth+1) -1;
//Math.pow 是 Java 中用于计算一个数的指数的函数。它接受两个参数:基数和指数,并返回基数的指数次方的结果。
//需要注意的是,Math.pow 返回的结果是一个 double 类型,即使输入的参数是整数类型,返回的结果也将是 double 类型。如果需要得到整数类型的结果,可以使用强制类型转换来将其转换为整数类型。
}
return comPleteBinaryTree(root.left) +
comPleteBinaryTree(root.right) +1;
}
}