数组实现双端队列-判断是不是完全二叉树

在这里插入图片描述

求解代码

不是完全二叉树主要就两种情况：

1.有右节点无左节点

2.如果是孩子不全的节点，则接下来必须全是叶子节点，否则就不是完全二叉树，对应设置一个leaf变量。

队列双指针：left=队头(出队)，right=队尾(入队)

leaf 变量的含义：

是否已经进入【叶子节点阶段】，也可以理解为后续所有节点都必须是「无孩子的叶子节点」，初始值false表示「还没到这个阶段」。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


	public static int MAXN = 101;
	public static TreeNode[] queue = new TreeNode[MAXN];
	public static int left,right;


    public boolean isCompleteTree (TreeNode root) {
        if(root==null){
			return true;
		}

		left=right=0;

		queue[right++]=root;

		boolean leaf = false;
		while (left<right) {
			root = queue[left++];

			if(leaf&&(root.left!=null||root.right!=null)){
				return false;
			}

			if(root.left==null&&root.right!=null){
				return false;
			}

			if(root.left!=null){
				queue[right++]=root.left;
			}

			if (root.right!=null) {
				queue[right++]=root.right;
			}

			if (root.left==null||root.right==null) {
				leaf = true;
			}
		}
		return true;

    }