2021-07-11：给定一个棵完全二叉树，返回这棵树的节点个数，要求时间复杂度小于O(树的节点数)。
2021-07-11：给定一个棵完全二叉树，返回这棵树的节点个数，要求时间复杂度小于O(树的节点数)。
福大大 答案2021-07-11：
右树最左节点层数==左树最左节点层数，左树是满二叉树，统计左树节点个数，递归右树。
右树最左节点层数!=左树最左节点层数，右树是满二叉树，统计右树节点个数，递归左树。
时间复杂度：O(logN的平方)。空间复杂度：O(logN)。
代码用golang编写。代码如下：
package mainimport "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 intLeft *NodeRight *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}
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class14/Code04_CompleteTreeNodeNumber.java)