给出一个完全二叉树,求出该树的节点个数。
来源:力扣(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 为判断当前位置是否存在。