115th LeetCode Weekly Contest Check Completeness of a Binary Tree

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]

Output: true

Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]

Output: false

Explanation: The node with value 7 isn't as far left as possible.

Note:

The tree will have between 1 and 100 nodes.

常规题

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

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

 * }

 */

class Solution {

    public boolean isCompleteTree(TreeNode root) {

        if(root == null)

            return true;

        Queue<TreeNode>queue = new LinkedList<>();

        boolean leaf = false; //如果碰到了 某个结点孩子不全就开始　判断是不是叶子这个过程

        queue.add(root);

        TreeNode top = null,L = null,R = null;

        while(!queue.isEmpty()){

            top = queue.poll();

            L = top.left;  R = top.right;

            //第一种情况

            if((R != null && L == null))

                return false;

            //第二种情况  开启了判断叶子的过程 而且又不是叶子 就返回false

            if(leaf && (L != null || R != null)) //以后的结点必须是 左右孩子都是null

                return false;

            if(L != null)

                queue.add(L);

            //准确的说是　只要孩子不全就开启leaf，

            //但是前面已经否定了有右无左的情况，这里只要判断一下右孩子是不是为空就可以了(如果为空就开启leaf)

            if(R != null)

                queue.add(R);

            else

                leaf = true;

        }

        return true;

    }

}

巴特西

115th LeetCode Weekly Contest Check Completeness of a Binary Tree

最新文章

热门文章