GuilinDev

Lc0958

05 August 2008

958. Check Completeness of a Binary Tree

二叉树的完全性检验

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

完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）

DFS

我们从根节点开始搜索，并将根节点编号值设置为1。

2、然后搜索左子树，并传递其根节点值为2k。搜索右子树，并传递其根节点值为2k+1

3、在递归搜索过程中，记录节点个数n和当前最大节点编号值p。

4、最后判断最大节点值p和节点数n是否相等，相等则该二叉树是完全二叉树，否则不是。

递归边界：

1、题目规定树中最多有100个节点，如果节点编号k > 100，说明该二叉树不合法，返回false。

2、递归到叶子节点，子树递归结束，返回true。

O(n)，其中 n是树节点个数。

class Solution {
    int n = 0, p = 0;

    public boolean isCompleteTree(TreeNode root) {
        if (!dfs(root, 1)) {
            return false;
        }
        return n == p;
    }

    public boolean dfs(TreeNode root, int k) //k是当前节点编号
    {
        if (root == null) { //递归到了叶子节点
            return true;  
        }
        if (k > 100) {
            return false;
        }
        n++;
        p = Math.max(p, k); //记录节点数和最大节点编号值
        return dfs(root.left, 2 * k) && dfs(root.right, 2 * k + 1); //递归左右子树
    }
}

BFS

bfs遍历二叉树的套路，只不过在遍历时要判断一些条件，如果不符合题意就return false，用layerNum记录当前层如果不是最后一层的话应该有的节点数，即2的幂，用recNum记录每一层有的子节点数。用这两个变量来判断是否符合题意。

``java /**

Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
} */ class Solution { public boolean isCompleteTree(TreeNode root) { Queue queue = new LinkedList<>(); queue.add(root); double layerNum = 0.5; while (!queue.isEmpty()) { int size = queue.size(); layerNum *= 2; int recNum = 0; for (int i = 0; i < size; i++) { TreeNode temp = queue.poll(); if (size < layerNum && temp.left != null) return false; if (temp.left == null && temp.right != null) return false; if (temp.left != null) { if (recNum < i * 2) return false; queue.add(temp.left); recNum++; } if (temp.right != null) { queue.add(temp.right); recNum++; }
```
1
2
3
4
     }

 }
 return true;  } } ``
```

This site is open source. Improve this page.