【简单】判断一棵二叉树是否为完全二叉树－Java

二叉树是否为完全二叉树－Java"/>

【简单】判断一棵二叉树是否为完全二叉树－Java

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程

package live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree;import java.util.LinkedList;
import java.util.Queue;/*** 判断一棵二叉树是否为完全二叉树** 【题目】* 给定一个二叉树的头节点head，已知其中没有重复值的节点，实现一个函数判断这棵二叉树是否是完全二叉树。** 【难度】* 简单** 【解答】* 判断一棵二叉树是否是完全二叉树，依据以下标准会使判断过程变得简单且易实现：* １、按层遍历二叉树，从每层的左边向右边依次遍历所有的节点。* ２、如果当前节点有右孩子，但没有左孩子，直接返回false。* ３、如果当前节点并不是左右孩子都有，那之后的节点必须都为叶节点，否则返回false。* ４、遍历过程中如果不返回false，遍历结束后返回true。* 判断是否是完全二叉树的全部过程请参看如下代码中的isCBT方法。** @author Created by LiveEveryDay*/public class IsCBT {public static class Node {public int data;public Node left;public Node right;public Node(int data) {this.data = data;}}public static boolean isCBT(Node root) {if (root == null) {return true;}Queue<Node> queue = new LinkedList<>();boolean isLeaf = false;Node l = null;Node r = null;queue.offer(root);while (!queue.isEmpty()) {root = queue.poll();l = root.left;r = root.right;if ((isLeaf && (l != null || r != null)) || (l == null && r != null)) {return false;}if (l != null) {queue.offer(l);}if (r != null) {queue.offer(r);} else {isLeaf = true;}}return true;}public static void main(String[] args) {Node node1 = new Node(5);Node node2 = new Node(3);Node node3 = new Node(7);Node node4 = new Node(1);Node node5 = new Node(4);Node node6 = new Node(6);Node node7 = new Node(8);node1.left = node2;node1.right = node3;node2.left = node4;node2.right = node5;node3.left = node6;node3.right = node7;boolean r = isCBT(node1);System.out.printf("Is complete binary tree? %s", r);}}// ------ Output ------
/*
Is complete binary tree? true
*/