# 二叉树的完全性检验 - Check Completeness of a Binary Tree

【层级遍历 - 迭代】 【层级遍历 - 递归】

``````给定一个二叉树，确定它是否是一个完全二叉树。

``````

### Example:

``````输入：[1,2,3,4,5,6]

``````

``````输入：[1,2,3,4,5,null,7]

``````

## Solutions

 ``````1 2 3 4 5 6 7 `````` `````` public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } ``````

### Solution 【层级遍历 - 迭代】 ( 6ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 `````` ``````class Solution { public boolean isCompleteTree(TreeNode root) { if (root == null) { return false; } Queue queue = new LinkedList<>(); TreeNode curNode; queue.offer(root); while (true) { curNode = queue.poll(); if(curNode == null) { break; } queue.offer(curNode.left); queue.offer(curNode.right); } while (!queue.isEmpty()) { if (queue.poll() != null) { return false; } } return true; } } ``````

### Solution 【层级遍历 - 递归】 ( 5ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 `````` ``````class Solution { public boolean isCompleteTree(TreeNode root) { return helper(root)[0] >= 0; } public int[] helper(TreeNode node) { if (node == null) return new int[]{1, 0}; int[] leftRes = helper(node.left); if (leftRes[0] < 0) return leftRes; int[] rightRes = helper(node.right); if (rightRes[0] < 0) return rightRes; if (leftRes[1] == rightRes[1] && leftRes[0] == 1) { return new int[]{rightRes[0], leftRes[1] + 1}; } else if (leftRes[1] == rightRes[1] + 1 && rightRes[0] == 1) { return new int[]{0, leftRes[1] + 1}; } else return new int[]{-1, 0}; } } ``````

### Notes

`while`中的小优化，提高运行速度。