给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例:
代码语言：javascript复制输入:
1
/
2 3
/ /
4 5 6
输出: 6解题思路：
1，递归遍历整个二叉树，这个方法可以优化
2，计算左右子树的高度l,r
A,如果l＝r 说明左子树是满二叉树,节点数为 2^l-1，右子树需要递归计算
B,如果l＝r 1 说明右子树是满二叉树，节点数为2^r-1，左子树需要递归计算
3，树的节点数为 根（1）＋左子树的节点数＋右子树的节点数
代码语言：javascript复制/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func countNodes(root *TreeNode) int {
if root==nil{
return 0
}
l:=depth(root.Left)
r:=depth(root.Right)
if l==r{
return 1<<l countNodes(root.Right)
}
return 1<<r countNodes(root.Left)
}
func depth(root*TreeNode) uint{
if root==nil{
return 0
}
var l uint =0
for root!=nil{
root=root.Left
l
}
return l
}
