题解 | #判断是不是完全二叉树#
判断是不是完全二叉树
https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae
import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */ public class Solution { public boolean isCompleteTree (TreeNode root) { if(root == null) return true; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); TreeNode cur; boolean notComplete = false; while(!queue.isEmpty()){ cur = queue.poll(); if(cur == null){ notComplete = true; continue; } if(notComplete) return false; //此题与层序遍历不一样的点,没有判断左右子树是否为空,经过草稿纸上画图可以得知: //如果是完全二叉树,那么当层序遍历出现空节点时,一定能保证此空节点是第在h层 //因为是从左往右遍历,当出现空结点之后,后续不可能再出现非空节点,否则就说明: //左子树空而右子树非空,或者是叶子节点不仅仅位于h层和h-1层,这样都可以判断完全二叉树 queue.offer(cur.left); queue.offer(cur.right); } return true; } }#判断完全二叉树#