给定一个棵完全二叉树,返回这棵树的节点个数,要求时间复杂度小于O(树的节点数)。
右树最左节点层数==左树最左节点层数,左树是满二叉树,统计左树节点个数,递归右树。
右树最左节点层数!=左树最左节点层数,右树是满二叉树,统计右树节点个数,递归左树。
时间复杂度:O(logN的平方)。空间复杂度:O(logN)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
head := &Node{}
head.Left = &Node{}
head.Right = &Node{}
head.Left.Left = &Node{}
head.Left.Right = &Node{}
head.Right.Left = &Node{}
ret := nodeNum(head)
fmt.Println(ret)
}
type Node struct {
Val int
Left *Node
Right *Node
}
// 请保证head为头的树,是完全二叉树
func nodeNum(head *Node) int {
if head == nil {
return 0
}
return bs(head, 1, mostLeftLevel(head, 1))
}
// 当前来到node节点,node节点在level层,总层数是h
// 返回node为头的子树(必是完全二叉树),有多少个节点
func bs(node *Node, Level int, h int) int {
if Level == h {
return 1
}
if mostLeftLevel(node.Right, Level+1) == h {
return (1 << (h - Level)) + bs(node.Right, Level+1, h)
} else {
return (1 << (h - Level - 1)) + bs(node.Left, Level+1, h)
}
}
// 如果node在第level层,
// 求以node为头的子树,最大深度是多少
// node为头的子树,一定是完全二叉树
func mostLeftLevel(node *Node, level int) int {
for node != nil {
level++
node = node.Left
}
return level - 1
}
执行结果如下: