若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
判断流程 :1.如果二叉树中某个节点有右孩子, 没有左孩子, 那么不是完全二叉树。
2.如果遇到不双全的节点(有左孩子, 没有右孩子 || 没有左孩子,没有右孩子), 那么后面遍历的节点必须都是叶子节点(没有左右孩子), 否则不是完全二叉树。
public class 判断是否完全二叉树 { public class CompleteBinaryNode { private CompleteBinaryNode left; private CompleteBinaryNode right; private int val; public CompleteBinaryNode(int v) { this.val = v; } } public boolean process(CompleteBinaryNode head) { if (head == null) { return true; } boolean leaf = false; Queuequeue = new linkedList<>(); queue.offer(head); while (!queue.isEmpty()) { CompleteBinaryNode cur = queue.poll(); //判断是否完全二叉树的两个条件 //1.如果当前节点左孩子为空, 右孩子不为空 那么不是完全二叉树 if ((cur.left == null && cur.right != null) //2.如果之前遇到过有节点孩子不满, 那么之后的节点必须都是叶子节点(没有孩子节点) //否则不是完全二叉树 || (leaf && (cur.left != null || cur.right != null))) { return false; } if (cur.left != null) { queue.offer(cur.left); } if (cur.right != null) { queue.offer(cur.right); } //3.第一次遇到孩子节点不满的标记 if (cur.left == null || cur.right == null) { leaf = true; } //不满的两种情况 1.无左孩子有右孩子 2.无左右孩子 3.无左孩子有右孩子已经判断过了可以化简 // if (cur.left != null && cur.right == null) { // leaf = true; // } // if (cur.left == null && cur.right == null) { // leaf = true; // } } return true; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)