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

using System;
using System.Collections.Generic;

/*
public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode (int x)
    {
        val = x;
    }
}
*/

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public int Depth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return Math.Max(Depth(root.left), Depth(root.right)) + 1;
    }
    public bool isCompleteTree(TreeNode root) {
        // write code here
        if (root == null) return false;
        if (root.left == null && root.right == null) return true;
        int h = Depth(root);
        List<List<int>> res = new List<List<int>>();
        Queue<TreeNode> queue = new Queue<TreeNode>();
        Queue<TreeNode> fzQueue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int level = 0;
        while (queue.Count != 0) {
            List<int> temp = new List<int>();
            int size = queue.Count;
            Queue<TreeNode> tempQueue = new Queue<TreeNode>();
            for (int i = 0; i < size; i++) {
                TreeNode t = queue.Dequeue();
                temp.Add(t.val);
                tempQueue.Enqueue(t);
                if (t.left != null)
                    queue.Enqueue(t.left);
                if (t.right != null)
                    queue.Enqueue(t.right);
            }
            ++level;
            if (level == h - 1) {
                fzQueue = tempQueue;
            }
            res.Add(temp);
        }
        for (int i = 0; i < res.Count - 1;
                i++) { //一直倒数第二行，每一行都要满结点
            if (res[i].Count < Math.Pow(2, i))
                return false;
        }
        Queue<TreeNode> ls = new Queue<TreeNode>(fzQueue);
        List<TreeNode> treeNodeList = new List<TreeNode>(ls);
        for (int i = 0; i < treeNodeList.Count - 1;
                i++) { //处理最后一层，倒数第二层兄弟结点之间，左边的都没有子结点的情况，而右边的有子结点
            for (int j = i + 1; j < treeNodeList.Count; j++) {
                if (treeNodeList[i].left == null && treeNodeList[i].right == null &&
                        (treeNodeList[j].left != null || treeNodeList[j].right != null))
                    return false;
                if (treeNodeList[i].left != null && treeNodeList[i].right == null &&
                        (treeNodeList[j].left != null || treeNodeList[j].right != null))
                    return false;
            }

        }
        while (fzQueue.Count !=
                0) { //处理最后一层左子树不存在，右子树存在的情况
            TreeNode treeNode = fzQueue.Dequeue();
            if (treeNode.left == null && treeNode.right != null)
                return false;
        }
        return true;
    }
}