一.题目

leetcode:222

完全二叉树节点个数
用层序遍历可以做，就是套模板，

层序遍历解法

func countNodes(root *TreeNode) int {
    if root==nil{
        return 0
    }
    lis := list.New()
    lis.PushBack(root)
    num := 1
    for lis.Len()>0{
        length := lis.Len()
        for i:=0;i<length;i++{
            node := lis.Remove(lis.Front()).(*TreeNode)
            if node.Left!=nil{
                lis.PushBack(node.Left)
                num++
            }
            if node.Right!=nil{
                lis.PushBack(node.Right)
                num++
            }

        }
    }
    return num
}

递归解法

func countNodes(root *TreeNode) int{
    var traversal func(node *TreeNode)
    num := 0
    traversal = func(node *TreeNode){
        if node==nil{
            return 
        }
        num++
        traversal(node.Left)
        traversal(node.Right)
    }
    traversal(root)
    return num
}

推荐：利用完全二叉树特性的递归解法

有一点不懂的是：为什么countNodes(root.Left)这个递归就可以返回左子树的个数，并没有返回任何值呀？

func countNodes(root *TreeNode) int {
    if root==nil{
        return 0
    }
    lefth, righth := 0,0
    left := root.Left
    right := root.Right
    for left!=nil{
        lefth++
        left = left.Left
    }
    for right!=nil{
        righth++
        right = right.Right
    }
    if righth==lefth{
        // 说明是完全二叉树,根据公式来，计算深度是优化
        return (2<<lefth)-1
    }
    // 不相等，不能优化
    return countNodes(root.Left) + countNodes(root.Right) + 1
}