주어진 이진 트리가 완전한지 확인하십시오

문제 정책

"주어진 이진 트리가 완전한지 여부 확인"문제는 이진 트리의 루트가 주어 졌음을 나타내며 트리가 완전한지 여부를 확인합니다. 완전한 이진 트리는 마지막 레벨을 제외한 모든 레벨이 채워져 있고 마지막 레벨의 노드는 가능한 한 남아 있습니다.

예

입력

핀

true

입력

핀

false

접근

A 완전한 이진 트리 하는 이진 트리 마지막 레벨을 제외한 모든 레벨이 채워지고 마지막 레벨 노드는 가능한 한 남아 있습니다.

이진 트리가 완전한지 확인하려면 다음을 사용할 수 있습니다. 레벨 순서 순회 나무의.

1. 왼쪽 및 오른쪽 자식이 모두 null이 아닌 노드로 전체 노드를 정의합니다.
2. 완전한 트리의 경우 레벨 순서 순회 중에 완료되지 않은 노드가 표시되면이 노드 이후의 모든 노드가 리프 노드 여야하며 그렇지 않으면 트리가 완료되지 않습니다.
3. 또한 오른쪽 자식이 null이 아니고 왼쪽 자식이 null 인 노드가 있으면 트리가 완전하지 않습니다.

암호알고리즘

1. 루트가 null이면 true를 반환합니다.
2. 큐를 만들고 루트 노드를 푸시합니다. 부울 변수 foundNonComplete를 false로 초기화합니다.
3. 대기열이 비어 있지 않은 동안 4 단계를 반복합니다.
4. 대기열에서 노드를 제거하고 현재 노드로 둡니다. 현재 노드의 왼쪽 자식이 null이 아니면 foundNonComplete가 true인지 확인하고, 그렇다면 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

복잡성 분석

시간 복잡성

의 위에), 바이너리 트리의 레벨 순서 순회 만 수행했기 때문입니다. 레벨 순서 순회는 트리 노드를 통과합니다. 따라서 알고리즘은 선형 시간 복잡도로 실행됩니다.

공간 복잡성

의 위에), 레벨 순서 순회에는 알고리즘이 선형 공간 복잡성을 갖도록 만드는 대기열의 사용이 필요합니다.