已知一棵完全二叉树, 求其节点的个数
要求: 时间复杂度低于O(N), N为这棵树的节点个数
public int countNodes(TreeNode root) {
if (root == null) return 0;
return bs(root,1,heightOfCompleteTree(root,1));
}
public static int heightOfCompleteTree(TreeNode root,int level){
while (root != null){
root = root.left;
level++;
}
return level-1;
}
public static int bs(TreeNode root,int level, int height){
if (level == height ) return 1;
if (heightOfCompleteTree(root.right,level+1) == height){
return (1<<(height - level)) + bs(root.right,level+1,height);
}else {
return (1<<(height - level - 1)) + bs(root.left,level+1,height);
}
}
注意:>> 与 <<的用法:
System.out.println( 1 << 2+2 ); 输出结果为16
>> 与 << 的运算优先级比 + - 要低
这里的主要两个逻辑为:
public static int heightOfCompleteTree(TreeNode root,int level){
while (root != null){
root = root.left;
level++;
}
return level-1;
}
这个函数的意思是:以level层的节点root计算这个树的最大的深度。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。