题解 | #判断是不是完全二叉树#

思路：排除几种错误的类型：空树、除去最后一层其他层没满、最后一层的叶节点不符合要求。解决方案是先根据层序遍历得到分层的、每一层的结点，再分上述情况进行判定。

package main
import . "nc_tools"
import "math"
/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return bool布尔型
*/
func isCompleteTree(root *TreeNode) bool {
	// write code here
    //改进的层序遍历，得到每一层的结点
	orderByNode := levelOrderByNode(root)
    //空树直接返回false
	if len(orderByNode) < 1 {
		return false
	}
    //只有一个结点返回true
	if len(orderByNode) == 1 {
		return true
	}
    //对于不包括最后一层的每一层，结点个数应该满足的条件n=2^i
	for i := 0; i < len(orderByNode)-2; i++ {
		if float64(len(orderByNode[i])) != math.Pow(float64(2), float64(i)) {
			return false
		}
	}
    //对于最后一层结点的情况讨论如下：
	for i := 0; i < len(orderByNode[len(orderByNode)-2]); i++ {
    //假设最后一层的上一层的某个结点的左子树为空，
		if orderByNode[len(orderByNode)-2][i].Left == nil  {
        //如果右子树不为空，则不符合要求
			if  orderByNode[len(orderByNode)-2][i].Right != nil {
				return false
			}
            //左右子树均为空，但是后面的结点的左右子树存在，则不符合
			for j := i+1; j <len(orderByNode[len(orderByNode)-2]) ; j++ {
				if orderByNode[len(orderByNode)-2][j].Right != nil || orderByNode[len(orderByNode)-2][j].Left != nil{
					return false
				}
			}
		}
        //假设最后一层的上一层的某个结点的右子树为空，
        if orderByNode[len(orderByNode)-2][i].Right == nil {
        //则后面不应该再有别的叶节点
			for j := i + 1; j < len(orderByNode[len(orderByNode)-2]); j++ {
				if orderByNode[len(orderByNode)-2][j].Right != nil || orderByNode[len(orderByNode)-2][j].Left != nil {
					return false
				}
			}
		}
	}
	return true
}
//层序遍历，获得每一层的结点
func levelOrderByNode(root *TreeNode) [][]*TreeNode {
	result := make([][]*TreeNode, 0)
	var dfs func(*TreeNode, int)
	dfs = func(node *TreeNode, level int) {
		if node == nil {
			return
		}
		if level == len(result) {
			result = append(result, []*TreeNode{})
		}
		result[level] = append(result[level], node)
		dfs(node.Left, level+1)
		dfs(node.Right, level+1)
	}
	dfs(root, 0)
	return result
}