[数据结构与算法]LeetCode 958. 二叉树的完全性校验

题目描述

校验一颗二叉树是否是完全二叉树。

思路

完全二叉树的特点，是树中的所有节点，在每一层都是从左到右依次填充，并且除了最后一层，其余所有层都是满节点的状态。我们可以根据这个特点，推导出一些性质，用来判断一棵树是否是完全二叉树。

思路1

利用节点下标和节点数量的关系。

设根节点下标为1，则一颗完全二叉树的层序遍历，其下标数组一定是1,2,3,4,5,....,n，最后一个节点的下标就等于节点数量。

我们可以遍历整颗二叉树，在遍历的过程中，记录当前的节点数量和最大下标，遍历结束后，最大下标和节点数量相等，就说明是一颗完全二叉树，否则不是（这个条件是充要条件）。

代码：（DFS）

class Solution {
    int n = 0; // 节点数量
    int maxIndex = 0; // 当前最大下标
    public boolean isCompleteTree(TreeNode root) {
        // dfs因为没有按层遍历, 所以对于完全二叉树, dfs不能保证n和maxIndex时时刻刻相等
        // 所以必须要遍历完整棵树, 再判断最终的n和maxIndex
        dfs(root, 1);
        return n == maxIndex;
    }

    // i 是当前节点 x 的下标
    private void dfs(TreeNode x , int i) {
        if (x == null) return;
        // 访问当前节点
        n++;
        maxIndex = Math.max(maxIndex, i);
        dfs(x.left, i * 2);
        dfs(x.right, i * 2 + 1);
    }
}

代码：（BFS）

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        int n = 0, maxIndex = 0;
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<Integer> indexQueue = new LinkedList<>();
        if (root != null) {
            nodeQueue.offer(root);
            indexQueue.offer(1);
        }

        while (!nodeQueue.isEmpty()) {
            TreeNode x = nodeQueue.poll();
            int i = indexQueue.poll();
            n++;
            maxIndex = Math.max(maxIndex, i);
            // 若是完全二叉树, 层序遍历能够保证n和maxIndex每时每刻都要相等, 因此可以提前结束
            if (n != maxIndex) return false;
            if (x.left != null) {
                nodeQueue.offer(x.left);
                indexQueue.offer(2 * i);
            }
            if (x.right != null) {
                nodeQueue.offer(x.right);
                indexQueue.offer(2 * i + 1);
            }
        }
        return n == maxIndex;
    }
}

思路2

若是完全二叉树，按照层序遍历，中间是不会出现空隙的。故在BFS过程中，如果在某一行遇到一个空节点，则后续所有的节点都应当为空。

注意这种解法，需要对空节点也进行插入，队列中会包含最后一层的后面所有空节点，以及最后一层左侧每个非空节点的2个空子节点。

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        boolean isReachNull = false;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 不管是否为空都要插入
        while (!queue.isEmpty()) {
            TreeNode x = queue.poll();
            if (x == null) {
                isReachNull = true;
                continue;
            }
            if (isReachNull) return false; // 后序所有节点都必须为空
            queue.offer(x.left);
            queue.offer(x.right);
        }
        return true;
    }
}

思路3

没看题解前，自己的思路。代码有点冗长，不过还是记录一下。

完全二叉树的特点是，最后一层节点从左往右填充，其余每层都是满节点。于是先找到最后一层的位置，最后判断队列是否为空。注意在每一层，也要判断节点是否依次从左往右填充。

class Solution {
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.offer(root);
        boolean reachLastLayer = false;
        int fullSize = 1; // 当前层的满节点状态时, 节点的数量
        while (!queue.isEmpty()) {
            int size = queue.size();
            // 遍历当前这一层
            // 需要维护左侧节点
            TreeNode left = null;
            for (int i = 0; i < size; i++) {
                TreeNode x = queue.poll();
                if (x.left != null) {
                    queue.offer(x.left);
                    if (i > 0 && left == null) return false;
                    left = x.left;
                } else left = null;
                if (x.right != null) {
                    queue.offer(x.right);
                    if (left == null) return false;
                    left = x.right;
                } else left = null;
            }
            // 当前层遍历结束, 若已经到达最后一层, 则break
            if (reachLastLayer) break;
            fullSize <<= 1; // 下一层满节点时的节点数
            // 若当前层插入完毕后, 下一层没有达到满节点数, 则下一层就是最后一层
            if (fullSize != queue.size()) reachLastLayer = true;
        }
        return queue.isEmpty();
    }
}