958. Check Completeness of a Binary Tree

, ,

DFS

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
class Solution {
    private static class ResultHolder {
        private boolean isComplete = true;
    }

    public boolean isCompleteTree(TreeNode root) {
        ResultHolder resultHolder = new ResultHolder();
        Deque<Integer> pathHighQueue = new LinkedList<>();
        dfs(root, resultHolder, pathHighQueue, 0);
        return resultHolder.isComplete;
    }

    private void dfs(TreeNode root, ResultHolder resultHolder, Deque<Integer> pathHighQueue, int high) {
        if (!resultHolder.isComplete) {
            return;
        }

        if (root == null) {
            if (!pathHighQueue.isEmpty() && (high > pathHighQueue.getLast() || high < pathHighQueue.getFirst() - 1)) {
                resultHolder.isComplete = false;
                return;
            }

            pathHighQueue.add(high);
        } else {
            dfs(root.left, resultHolder, pathHighQueue, high + 1);
            dfs(root.right, resultHolder, pathHighQueue, high + 1);
        }
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        boolean nullNodeHasAppeared = false; // 注意该变量在全局维度声明，而不是在单层内部
        Queue<TreeNode> queue = new LinkedList<>(); // 队列中包含空节点
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                nullNodeHasAppeared = true;
            } else {
                if (nullNodeHasAppeared) {
                    return false;
                }

                queue.offer(node.left);
                queue.offer(node.right);
            }
        }

        return true;
    }
}

关键点：空节点出现后不能再出现非空节点，即空节点只能存在于末尾，无需关注层序遍历。

References

958. Check Completeness of a Binary Tree