怎么计算一棵完全二叉树的节点个数
程序员文章站
2022-05-16 10:08:19
...
题目:已知一棵完全二叉树,求其节点的个数
要求:时间复杂度低于O(N),N为这棵树的节点个数
完全二叉树的概念就不多叙述了。
讲讲思路:题目的要求是时间复杂度低于O(N),所以遍历的方式就不用考虑了,根据完全二叉树的特点可以知道,从头节点head开始一直往左走可以可以到达完全二叉树的最底层,而就是可以计算出二叉树的高度H了,(默认给定的一定是完全二叉树,,,)
1)当头结点的右子节点作为头节点来计算他的高度h+1等于H的时候,说明head的左子树是一棵满二叉树,可以使用公式t = 2^level-1,也就是节点个数t等于2的层数次方-1。这个时候,发现右子树可以使用递归的方式计算,因为自问题与原问题是一致的。
2)当头结点的右子节点作为头节点来计算他的高度h+1不等于H的时候,说明head的右子树是一颗满二叉树。而左子树同(1),应该使用递归的方式解决。
下面看代码:
public class C08_CompleteTreeNodeNumber {
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int value){
this.value = value;
}
}
public static int nodeNum(Node head){
if(head==null){
return 0;
}
return process(1, head, totalHeigh(head, 1));
}
//当前节点的层数,当前节点,整颗二叉树的高度(这个是一直不变的)
public static int process(int level,Node cur,int h){
if(level==h){//到了最后一层
return 1;
}
//如果右子树高度+1等于树的高度,递归计算右子树,而左子树是一个满二叉树,用公式计算
if(totalHeigh(cur.right, level+1)==h){
//位运算<<一定要括起来
return (1<<(h-level)) + process(level+1, cur.right, h);
}
//如果右子树高度+1不等于树的高度,递归计算左子树,右子树是一颗满二叉树,用公式计算
else {
return (1<<(h-level-1)) + process(level+1, cur.left, h);
}
}
public static int totalHeigh(Node cur,int level){
while(cur!=null){
level++;
cur = cur.left;
}
return level-1;
}
public static void main(String[] args) {//test
Node head = new Node(2);
head.left = new Node(3);
head.right = new Node(3);
head.left.left = new Node(3);
//head.left.right = new Node(3);
//head.right.left = new Node(3);
System.out.println(nodeNum(head));
}
}
原文:https://blog.csdn.net/qq_38238041/article/details/79547490
上一篇: 已知一棵完全二叉树,求其节点的个数
下一篇: 已知一棵完全二叉树,求其节点的个数