判断一棵树是否是完全二叉树

根据完全二叉树的定义，如果二叉树上某个结点有右孩子无左孩子则一定不是完全二叉树；否则如果二叉树上某个结点有左孩子而没有右孩子，那么该结点所在的那一层上，该结点右侧的所有结点应该是叶子结点，否则不是完全二叉树。

import java.util.LinkedList;
import java.util.Queue;
public class tmp {
	public static class Node{  //一个静态内部类
		int data;
		Node left;
		Node right;
		public Node(int data) {
			this.data = data;
		}
	}
	public static boolean isCompleteBtree(Node root) {
		if(root == null) {
			return true;
		}
		Queue<Node> queue = new LinkedList<Node>();
		queue.offer(root);
		boolean leaf = false;
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			//左空右不空
			if(node.left == null && node.right != null) {
				return false;
			}
			//如果开启了叶子结点阶段，结点不能有左右孩子
			if(leaf && (node.left != null || node.right != null)) {
				return false;
			}
			//将下一层要遍历的加入到队列中
			if(node.left != null) {
				queue.offer(node.left);
			}
			if(node.right != null) {
				queue.offer(node.right);
			} else {
				leaf = true;
			}
		}
		return true;
	}
	public static void main(String[] args) {
		Node root = new Node(1);
		root.left = new Node(2);
		root.right = new Node(3);
		root.left.right = new Node(4);
		System.out.println(isCompleteBtree(root));
	}
}

判断一棵树是否是完全二叉树

原文：https://www.cnblogs.com/treasury/p/13258462.html