LeetCode 958. 二叉树的完全性检验 层序遍历BFS、DFS题解，理解BFS、DFS。

题目

958. 二叉树的完全性检验

https://leetcode.cn/problems/check-completeness-of-a-binary-tree/

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

思路

题干中提供了完全二叉树的性质。

借此我们也回顾下关于树的基本知识： https://github.com/redolog/algorithm-java/blob/main/doc/Tree.md

判断二叉树是否完全：

  • 我们可以借助父子节点下标的特性，即遍历，判断节点数与节点最大下标是否匹配；
  • 也可以层序遍历，判定是否有空节点出现在非空节点同层左侧；
  • 以上我们分别使用DFS深度优先、BFS广度优先的写法完成；

DFS深度优先

思路

判断节点数与节点最大下标是否匹配。

复杂度分析

时间

逐个遍历树所有节点，O(n)时间复杂度。

空间

递归栈空间有额外开销，每个节点递归一次，空间复杂度O(n)。

代码

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

/**
    * 下标指针，左子 i=2*parentI+1 右子 i=2*parentI+2
    */
int maxIdx;
/**
    * 遍历指针，从0开始计数
    */
int n;

/**
    * dfs深度优先遍历，判断遍历数n与最后节点的下标是否满足 完全二叉树定义
    * <p>
    * 执行用时：
    * 0 ms
    * , 在所有 Java 提交中击败了
    * 100.00%
    * 的用户
    * 内存消耗：
    * 41.1 MB
    * , 在所有 Java 提交中击败了
    * 14.91%
    * 的用户
    * 通过测试用例：
    * 119 / 119
    */
public boolean isCompleteTreeWithDfs(TreeNode root) {
    dfs(root, 0);
    return n - 1 == maxIdx;
}

/**
    * dfs深度优先遍历
    *
    * @param node    当前节点
    * @param parentI 父节点下标
    */
private void dfs(TreeNode node, int parentI) {
    if (null == node) {
        return;
    }

    maxIdx = Math.max(maxIdx, parentI);
    ++n;

    dfs(node.left, 2 * parentI + 1);
    dfs(node.right, 2 * parentI + 2);
}

BFS广度优先

思路

判定是否有空节点出现在非空节点同层左侧。

代码

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40

 /*
    * 执行用时：
    * 1 ms
    * , 在所有 Java 提交中击败了
    * 65.86%
    * 的用户
    * 内存消耗：
    * 40.6 MB
    * , 在所有 Java 提交中击败了
    * 80.89%
    * 的用户
    * 通过测试用例：
    * 119 / 119
    */
public boolean isCompleteTree(TreeNode root) {
    if (root == null) {
        return true;
    }
    Queue<TreeNode> level = new LinkedList<>();
    level.offer(root);
    // 一轮中如果出现先有null再有非null，即出现了非完全的情况
    boolean hasNull = false;
    while (!level.isEmpty()) {
        int size = level.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = level.poll();
            if (node == null) {
                hasNull = true;
                continue;
            }
            // 到这里肯定不为null
            if (hasNull) {
                return false;
            }
            level.offer(node.left);
            level.offer(node.right);
        }
    }
    return true;
}

复杂度分析

时间

依然是遍历整个树，一直到最后一层，时间复杂度O(n)。

空间

额外使用一个队列记录层序，空间复杂度O(n)。

Ref