完全二叉树结点个数
给出一个完全二叉树，求出该树的节点个数。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/count-complete-tree-nodes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
输入:
1
/ \
2 3
/ \ /
4 5 6
输出: 6解决方案
对于该问题的第一反应是直接dfs统计时间复杂度为O(N),其中N为结点数目。但是没有使用到完全二叉树的特性。
由于该树为完全二叉树，可以先计算得到其层数记做level（从0开始），其第0层到level - 1层中元素的数目为2 ^ level - 1个。第level层最少有一个结点，最多有2^level个结点，因此结点数目为[2 ^ level, 2 ^ (level + 1) - 1]，此时就可二分结果了。若给定数目cur存在，则left = cur，若cur不存在，则right = cur - 1。
对于给定cur判断其是否存在，只需依次从高到低位遍历cur的二进制位，若为0则为当前结点的左子树，为1则为当前结点的右子树，最终即可找到当前cur所对应的那个结点，判断其是否存在即可。
func countNodes(root *TreeNode) int {
if root == nil{
return 0
}
level := 0
for cur := root; cur.Left != nil; cur = cur.Left{
level++
}
left := 1 << level
right := 1 << (level + 1) - 1
mid := 0
for left < right{
// 此处需要注意的是二分时优先选择靠后的位置
mid = left + (right - left + 1) / 2;
if contains(root, mid, level){
left = mid
}else{
right = mid - 1
}
}
return left
}
func contains(root *TreeNode, mid, level int) bool{
cur := root
for i := level - 1; i >= 0; i--{
if (mid >> i) & 1 == 1{
cur = cur.Right
}else{
cur = cur.Left
}
if cur == nil{
return false
}
}
return true
}时间复杂度为O（log N * log N）其中N为结点数目。第一个log N 为二分答案，第二个log N 为判断当前位置是否存在。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-11-24，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录