【题目】
判断一棵树是否为完全二叉树。
【分析】
1、按层遍历二叉树，从每层的左边向右边依次遍历所有的节点
2、如果当前结点有右节点，但没有左节点，直接返回false
3、如果当前节点并不是左右两个节点全有，那么之后的节点都必须为叶节点，否则返回false
【代码】
package zyc.binaryTree;import java.util.LinkedList;
import java.util.Queue;public class P151_CBT {/*** 是否完全二叉树** @param node* @return*/public static boolean isCbt(Node node) {if (null == node) {return true;}Queue<Node> queue = new LinkedList<Node>();queue.add(node);boolean allLeaf = false;while (!queue.isEmpty()) {Node cur = queue.poll();if ((cur.left == null && cur.right != null) || (allLeaf && cur.left != null)) {return false;}if (cur.left != null) {queue.add(cur.left);}if (cur.right != null) {queue.add(cur.right);} else {allLeaf = true;}}return true;}public static void main(String[] args) {Node node = new Node(1);node.left = new Node(2);node.left.left = new Node(1);node.left.right = new Node(1);node.right = new Node(1);node.right.left = new Node(1);node.right.right = new Node(1);node.left.left.right = new Node(1);boolean cbt = isCbt(node);System.out.println(cbt);}public static class Node {public int value;public Node left;public Node right;public Node(int value) {this.value = value;}}}