方法一:层序遍历,只要节点不连续,返回false
class Solution { public boolean isCompleteTree(TreeNode root) { Queue<TreeNode> queue=new LinkedList<>(); TreeNode prev=root; queue.add(root); while (!queue.isEmpty()){ TreeNode node=queue.remove(); //如果前一个为空后一个不为空则返回false if (prev==null&&node!=null){ return false; } //将子节点加入到队列中 if (node!=null){ queue.add(node.left); queue.add(node.right); } prev=node; } return true; } }
方法二:DFS统计总节点个数是否等于完全二叉树最大需求节点个数
class Solution { int size = 0; // 总结点个数 int maxCode; // 最大需求节点个数 public boolean isCompleteTree(TreeNode root) { helper(root, 1); return size == maxCode ? true : false; } public void helper(TreeNode root, int code){ if(root == null) return; size++; maxCode = Math.max(maxCode, code); helper(root.left, 2*code); helper(root.right, 2*code + 1); } }