检查给定的二叉树是否完整


难度级别
经常问 Alation 美国运通卡 Databricks 氧气钱包 Spotify
二叉树 队列

问题陈述

问题“检查给定的二叉树是否完整”指出您已获得二叉树的根,请检查该树是否完整。 完整的二叉树具有除最后一级之外的所有所有等级,并且最后一级中的节点尽可能保留。

例子

输入

检查给定的二叉树是否完整

true

输入

检查给定的二叉树是否完整

false

途径

A 完整的二叉树 二叉树 其中,除了最后一个级别,所有级别都已填充,并且最后一个级别的节点尽可能保留。

要检查二叉树是否完整,我们可以使用 级别顺序遍历 的树。

  1. 将完整的节点定义为左子节点和右子节点都不为null的节点。
  2. 对于完整的树,如果我们在级别顺序遍历期间看到一个不完整的节点,则该节点之后的所有节点都必须是叶节点,否则该树是不完整的。
  3. 同样,如果有一个节点,其右子节点不为空,而左子节点不为空,则树不完整。

算法

  1. 如果根为null,则返回true。
  2. 创建一个队列并将根节点推送到该队列。 将布尔变量foundNonComplete初始化为false。
  3. 当队列不为空时,请重复步骤4。
  4. 从队列中删除一个节点,使其成为当前节点。 如果当前节点的左子节点不为null,则检查foundNonComplete是否为true,如果为false,则返回false,否则将左子节点推送至队列,如果左子节点为null,则将foundNonComplete标记为true。 同样,如果正确的子代不为null,则检查foundNonComplete是否为true,如果是则返回false,否则将正确的子代推入队列,如果正确的子代为null,则将foundNonComplete标记为true。
  5. 如果到达步骤5,则返回true。

代码

用于检查给定的二叉树是否完整的Java代码

import java.util.LinkedList;
import java.util.Queue;
class CheckWhetherAGivenBinaryTreeIsCompleteOrNot {
    // class representing the node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static boolean isComplete(Node root) {
        // if root is null, return true
        if (root == null) {
            return true;
        }

        // create a queue to do level order traversal
        Queue<Node> queue = new LinkedList<>();
        // add the root node to queue
        queue.add(root);
        // initialize foundNonComplete as false
        boolean foundNonComplete = false;

        while (!queue.isEmpty()) {
            // remove a node from queue
            Node curr = queue.poll();
            if (curr.left != null) {
                // if a non complete node was found, return false
                if (foundNonComplete) {
                    return false;
                }
                // add the left child to queue
                queue.add(curr.left);
            } else {
                // if left child is null, this is a non complete node
                foundNonComplete = true;
            }

            if (curr.right != null) {
                // if a non complete node was found, return false
                if (foundNonComplete) {
                    return false;
                }
                // add the right child to queue
                queue.add(curr.right);
            } else {
                // if right child is null, this is a non complete node
                foundNonComplete = true;
            }
        }

        // reaching here means tree is complete
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(5);
        System.out.println(isComplete(root1));

        // Example 2
        Node root2 = new Node(9);
        root2.left = new Node(8);
        root2.right = new Node(14);
        root2.left.left = new Node(10);
        root2.right.right = new Node(2);
        System.out.println(isComplete(root2));
    }
}
true
false

用于检查给定二叉树是否完整的C ++代码

#include <bits/stdc++.h> 
using namespace std; 

// class representing the node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

bool isComplete(Node *root) {
    // if root is null, return true
    if (root == NULL) {
        return true;
    }
    
    // create a queue to do level order traversal
    queue<Node*> q;
    // add the root node to queue
    q.push(root);
    // initialize foundNonComplete as false
    bool foundNonComplete = false;
    
    while (!q.empty()) {
        // remove a node from queue
        Node *curr = q.front();
        q.pop();
        if (curr->left != NULL) {
            // if a non complete node was found, return false
            if (foundNonComplete)
                return false;
            // add the left child to queue
            q.push(curr->left);
        } else {
            // if left child is null, this is a non complete node
            foundNonComplete = true;
        }
        
        if (curr->right != NULL) {
            // if a non complete node was found, return false
            if (foundNonComplete) 
                return false;
            q.push(curr->right);
        }
    }
    
    // reaching here means tree is complete
    return true;
}

int main() {
    // Example 1
    Node *root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);
    if (isComplete(root1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    Node *root2 = new Node(9);
    root2->left = new Node(8);
    root2->right = new Node(14);
    root2->left->left = new Node(10);
    root2->right->right = new Node(2);
    if (isComplete(root2)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

复杂度分析

时间复杂度

上), 因为我们只完成了二叉树的级别顺序遍历。 级别顺序遍历遍历树节点。 因此,该算法以线性时间复杂度运行。

空间复杂度

上), 级别顺序遍历需要使用队列,这使算法具有线性空间复杂度。