연결된 목록 표현에서 완전한 이진 트리 구성

난이도 중급
자주 묻는 질문 아마존
이진 트리 나무조회수 49

완전한 바이너리의 연결 목록 표현이 주어지면 나무. 연결 목록은 레벨 순서 순회 나무의. 완전한 이진 트리를 구성하는 알고리즘을 작성하십시오. 연결 목록 대표.

입력
1-> 2-> 3-> 4-> 5
산출
순회 순회
4 2 5 1 3

연결된 목록 표현에서 완전한 이진 트리 구성

완전한 이진 트리 생성을위한 알고리즘

완전한 이진 트리는 마지막 수준을 제외하고 모든 수준이 완전히 채워진 이진 트리이며 마지막 수준의 모든 노드는 가능한 한 남아 있습니다. 또한 완전한 트리가 배열을 통해 표현 될 때 배열의 인덱스 i에있는 노드는 인덱스 (2 * i + 1)에 왼쪽 자식이 있고 인덱스 (2 * i + 2)에 오른쪽 자식이 있습니다. 링크드리스트 표현에서 같은 것을 시각화 할 수 있습니다.
따라서 인덱스 0에있는 노드의 자식은 인덱스 1과 2에 있고, 인덱스 1에있는 노드의 자식은 인덱스 3과 4에있는 식입니다.

연결 목록 표현을 트리로 변환하는 아이디어는 연결 목록의 첫 번째 노드가 항상 트리의 루트라는 것입니다. 그래서 우리는 큐에 루트를 밀어 넣고, 트리에서 BFS를 수행하고 동시에 연결 목록을 트래버스하여 트리로 변환합니다. 트리의 모든 노드에 대해 링크 된 목록의 두 노드를 탐색합니다. 하나는 왼쪽 자식 용이고 다른 하나는 오른쪽 자식 용입니다.

  1. 대기열을 만듭니다.
  2. 연결 목록의 헤드를 대기열로 푸시합니다.
  3. 연결 목록의 끝에 도달하지 않은 동안 4 단계를 반복하십시오.
  4. 큐에서 노드를 제거하고 부모가되도록합니다. 목록에서 순회하면 첫 번째 노드는 부모의 왼쪽 자식이고 두 번째 노드는 부모의 오른쪽 자식입니다. 또한 왼쪽 및 오른쪽 자식을 대기열에 넣습니다.

완전한 이진 트리 구성을위한 JAVA 코드

import java.util.LinkedList;
import java.util.Queue;

public class ConstructCompleteBinaryTreeFromItsLinkedListRepresentation {
    // class representing node of a linked list
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }
    
    // class representing node of a binary tree
    static class TreeNode {
        int data;
        TreeNode left, right;

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

    // function to print inorder traversal of a tree
    private static void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static void constructCompleteBinaryTree(ListNode head) {
        if (head == null) {
            return;
        }

        // initialize root of the tree as head of linked list
        TreeNode root = new TreeNode(head.data);
        // create a queue
        Queue<TreeNode> q = new LinkedList<>();
        // push the root of the tree to the queue
        q.add(root);

        while (head != null) {
            // remove an element from the queue
            TreeNode parent = q.poll();

            // traverse in linked list
            head = head.next;
            if (head != null) {
                // this node of linked list is the left child of parent
                TreeNode leftChild = new TreeNode(head.data);
                parent.left = leftChild;
                // add left child to the queue
                q.add(leftChild);

                // traverse in linked list
                head = head.next;
                if (head != null) {
                    // this node of the linked list is the right child of parent
                    TreeNode rightChild = new TreeNode(head.data);
                    parent.right = rightChild;
                    // add right child to the queue
                    q.add(rightChild);
                }
            }
        }

        // print inorder traversal of the tree
        System.out.println("Inorder Traversal");
        inorder(root);
        System.out.println();
    }

    public static void main(String[] args) {
        // Example
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        constructCompleteBinaryTree(head);
    }
}
Inorder Traversal
4 2 5 1 3

완전한 이진 트리 생성을위한 C ++ 코드

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

// class representing node of a linked list
class ListNode {
    public:
    int data;
    ListNode *next;
    
    ListNode(int d) {
        data = d;
        next = NULL;
    }
};

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

// function to print inorder traversal of a tree
void inorder(TreeNode *root) {
    if (root != NULL) {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void constructCompleteBinaryTree(ListNode *head) {
    if (head == NULL) {
        return;
    }
    
    // initialize root of the tree as head of linked list
    TreeNode *root = new TreeNode(head->data);
    // create a queue
    queue<TreeNode *> q;
    // push the root of the tree to the queue
    q.push(root);
    
    while (head != NULL) {
        // remove an element from the queue
        TreeNode *parent = q.front();
        q.pop();
        
        // traverse in linked list
        head = head->next;
        if (head != NULL) {
            // this node of linked list is the left child of parent
            TreeNode *leftChild = new TreeNode(head->data);
            parent->left = leftChild;
            // add left child to the queue
            q.push(leftChild);
            
            // traverse in linked list
            head = head->next;
            if (head != NULL) {
                // this node of the linked list is the right child of parent
                TreeNode *rightChild = new TreeNode(head->data);
                parent->right = rightChild;
                // add right child to the queue
                q.push(rightChild);
            }
        }
    }
    
    // print inorder traversal of the tree
    cout<<"Inorder Traversal"<<endl;
    inorder(root);
    cout<<endl;
}

int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    constructCompleteBinaryTree(head);
    
    return 0;   
}
Inorder Traversal
4 2 5 1 3

복잡성 분석

시간 복잡성 = O (N)
공간 복잡성 = O (N)
여기서 n은 연결 목록의 요소 수입니다.

레퍼런스 1  참조 2

Translate »