Medium

题目描述

给定一个二叉树的根节点 root，判断它是否是一个完全二叉树。

在一个完全二叉树中，除了最后一层外，所有层都被完全填满，并且最后一层的所有节点都尽可能地向左排列。在最后一层 h 上，可以有 1 到 2^h 个节点。

示例 1：

输入：root = [1,2,3,4,5,6]
输出：true
解释：除最后一层外的每一层都是满的（即，含有节点值 {1} 的层和含有节点值 {2, 3} 的层），最后一层的所有节点（{4, 5, 6}）都尽可能地向左排列。

示例 2：

输入：root = [1,2,3,4,5,null,7]
输出：false
解释：值为 7 的节点没有尽可能靠向左侧。

约束条件：

  • 树中节点数目在范围 [1, 100] 内
  • 1 <= Node.val <= 1000

解题思路

解题思路

完全二叉树的关键特征是：除最后一层外所有层都被完全填满，且最后一层的节点都尽可能向左排列。

主要有两种解法：

解法一：层序遍历标记法（推荐） 使用层序遍历（BFS），关键观察：在完全二叉树中，一旦出现 null 节点，后续所有节点都必须是 null。我们可以设置一个标记，当遇到第一个 null 节点时设为 true，如果之后还遇到非 null 节点，说明不是完全二叉树。

解法二：节点编号法 给每个节点按照完全二叉树的方式编号（根节点编号1，左子节点编号2i，右子节点编号2i+1），统计总节点数n。如果是完全二叉树，最大编号应该等于节点总数n。

第一种方法更直观且空间复杂度更优，是推荐解法。算法流程：

  1. 使用队列进行层序遍历
  2. 将所有节点（包括null）都加入队列
  3. 设置flag标记是否遇到了null节点
  4. 如果flag为true时遇到非null节点，返回false
  5. 遍历完成返回true

代码实现

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if (!root) return true;
        
        queue<TreeNode*> q;
        q.push(root);
        bool flag = false;
        
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            
            if (!node) {
                flag = true;
            } else {
                if (flag) return false;
                q.push(node->left);
                q.push(node->right);
            }
        }
        
        return true;
    }
};

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        queue = collections.deque([root])
        flag = False
        
        while queue:
            node = queue.popleft()
            
            if not node:
                flag = True
            else:
                if flag:
                    return False
                queue.append(node.left)
                queue.append(node.right)
        
        return True

public class Solution {
    public bool IsCompleteTree(TreeNode root) {
        if (root == null) return true;
        
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        bool flag = false;
        
        while (queue.Count > 0) {
            TreeNode node = queue.Dequeue();
            
            if (node == null) {
                flag = true;
            } else {
                if (flag) return false;
                queue.Enqueue(node.left);
                queue.Enqueue(node.right);
            }
        }
        
        return true;
    }
}

var isCompleteTree = function(root) {
    if (!root) return true;
    
    const queue = [root];
    let flag = false;
    
    while (queue.length > 0) {
        const node = queue.shift();
        
        if (!node) {
            flag = true;
        } else {
            if (flag) return false;
            queue.push(node.left);
            queue.push(node.right);
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(w)

其中 n 是树中节点的数量，w 是树的最大宽度（最多的层的节点数），在最坏情况下为 O(n)。