递归
递归很简单，遍历整棵树即可，代码复杂度为O(n)
点击查看代码
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
return 1+countNodes(root.Left)+countNodes(root.Right)
}
二分查找
二分查找的思路如下图所示
最难的部分应该是判断某个节点是否存在，需要结合完全二叉树的性质，只要给出一个n就可以构造出从根节点到该叶子节点的路径，我们找到之后判断该节点是否为nil即可。
点击查看代码
func countNodes(root *TreeNode) int {
if root == nil {
return 0
}
var bigLeft, bigRight = getRange(root)
var left, right = bigLeft, bigRight
for left < right {
var mid = left + (right-left)/2
if ex(root, bigLeft, bigRight, mid) {
left = mid + 1
} else {
right = mid
}
}
return left - 1
}
//左闭右开
func getRange(root *TreeNode) (int, int) {
if root == nil {
return 0, 0
}
var res = 1
var node = root
for node.Left != nil {
res = res * 2
node = node.Left
}
return res, res * 2
}
func ex(root *TreeNode, left int, right int, n int) bool {
if root == nil {
return false
}
if root.Left == nil && root.Right == nil {
return n == 1
}
var node = root
for node != nil && left < right {
var mid = left + (right-left)/2
if right-left == 1 {
node = node.Left
break
}
if right-left == 2 {
if n == left {
node = node.Left
} else if n == left+1 {
node = node.Right
}
break
}
if left <= n && n < mid {
node = node.Left
right = mid
} else if mid <= n && n < right {
node = node.Right
left = mid
}
}
return node != nil
}