C++ 从链表表示构造完全二叉树

在这个问题中，我们将把链表转换成完全二叉树。

我们可以把链表看作一个数组。链表的第p个元素是二叉树的2*p + 1和2*p + 2元素的父节点。因此，我们可以遍历链表的每个元素并构建二叉树。

问题描述 −给定包含N个节点的链表。我们需要从给定的链表构建完全二叉树。同时，打印出二叉树的中序遍历。

注意 −在完全二叉树中，除了最后一层，树的所有层都是完全填充的。

示例

输入

L_head = 48 -> 142 -> 18 -> 72 -> 10 -> 12 -> 94 -> 45

输出

45, 72, 142, 10, 48, 12, 18, 94

48
                 /  \
                   142  18
              /  \  /  \
                 72  10 12 94
                /
               45

解释 - 中序遍历首先打印左子树，接着是根节点，最后是右子树。

输入

L_head = 2 -> 8 -> 4 -> 5

输出

5, 8, 2, 4

2
           /   \
          8     4
         /
        5

解释 − 我们已经打印了给定二叉树的中序遍历。

输入

L_head = NULL

输出

NULL

解释 - 二叉树为NULL，因为链表中没有任何节点。

方法

在链表中，第P个节点是二叉树中第(2P+1)和(2P+2)个节点的父节点。

我们将使用队列数据结构来跟踪二叉树的节点。在使用链表元素创建二叉树节点后，我们将树节点推入队列中。然后，在每次迭代中，我们从队列中弹出节点，从链表中获取下一个2个节点，并为当前节点创建左右子节点，并将它们与父节点连接起来。

算法

步骤1 - 为包含”val”整数变量和”next”指针的链表创建L_Node结构。

步骤2 - 为包含”val”整数和”left”、”child”指针的二叉树创建B_Node结构。

步骤3 - 接下来，定义insertInList()函数来创建链表。

步骤3.1 - 在insertInList()函数中，定义一个新的L_Node。

步骤3.2 - 初始化新节点的值。同时，将新节点的”next”指针初始化为头节点，以在链表的开始处插入新节点。

步骤3.3 - 更新头节点为新节点。

步骤4 - 定义createNewNode()函数来创建二叉树的新节点。

步骤5 - 定义listToBinary()函数将链表转换为二叉树。

步骤6 - 如果L_head为空，将B_head更新为NULL并执行返回语句。

步骤7 - 用链表的L_Node值创建一个新的二叉树节点，并将其存储在B_head中。同时，将B_head插入队列中，并将L_head指向下一个节点。

步骤8 - 遍历链表。

步骤8.1 - 从队列中弹出第一个节点，并将其存储在”parent”节点中。同时，创建”l_child”和”r_child”指针并初始化为NULL。

步骤8.2 - 为二叉树创建一个新节点，并将其初始化为L_head节点的值，然后将其存储在l_child节点中。

步骤8.3 - 将l_child节点插入队列，并将L_head移动到下一个节点。

步骤8.4 - 如果l_head不为空，创建一个新节点，并将其赋值给r_child节点。同时，将r_child节点插入队列，并将L_head移动到下一个节点。

步骤9 - 使用l_child和r_child节点更新父节点的左右指针。

步骤10 - 创建inorder()函数，以显示新创建树的中序遍历。

示例

#include <iostream>
#include <string>
#include <queue>
using namespace std;

// Structure for tree and linked list
struct L_Node {
    int val;
    L_Node *next;
};
struct B_Node {
    int val;
    B_Node *left, *right;
};
// To insert a node in a linked list
void InsertInList(struct L_Node **head, int new_val) {
    struct L_Node *temp_node = new L_Node;
    temp_node->val = new_val;
    // Insert node at start
    temp_node->next = (*head);
    // Change head node pointer
    (*head) = temp_node;
}
// For Creating a new node for the tree
B_Node *createNewNode(int val) {
    B_Node *temp_node = new B_Node;
    temp_node->val = val;
    temp_node->left = temp_node->right = NULL;
    return temp_node;
}
void listTOBinary(L_Node *L_head, B_Node *&B_head) {
    queue<B_Node *> que;
    // For empty linked list
    if (L_head == NULL) {
        B_head = NULL;
        return;
    }
    // Initialize the head node of the binary tree
    B_head = createNewNode(L_head->val);
    que.push(B_head);
    // Move list pointer
    L_head = L_head->next;
    // Traverse until we reach at the end of the list
    while (L_head) {
        // Take node from queue
        B_Node *parent = que.front();
        que.pop();
        // Add the next two nodes as a child of the parent node
        B_Node *l_child = NULL, *r_child = NULL;
        l_child = createNewNode(L_head->val);
        que.push(l_child);
        L_head = L_head->next;
        if (L_head) {
            r_child = createNewNode(L_head->val);
            que.push(r_child);
            L_head = L_head->next;
        }
        parent->left = l_child;
        parent->right = r_child;
    }
}
void inorder(B_Node *B_head) {
    if (B_head) {
        inorder(B_head->left);
        cout << B_head->val << " ";
        inorder(B_head->right);
    }
}
int main() {
    struct L_Node *L_head = NULL;
    InsertInList(&L_head, 45);
    InsertInList(&L_head, 94);
    InsertInList(&L_head, 12);
    InsertInList(&L_head, 10);
    InsertInList(&L_head, 72);
    InsertInList(&L_head, 18);
    InsertInList(&L_head, 142);
    InsertInList(&L_head, 48);
    B_Node *B_head;
    listTOBinary(L_head, B_head);
    cout << "The Inorder Traversal of the newly created Binary Tree is: \n";
    inorder(B_head);
    return 0;
}

输出

The Inorder Traversal of the newly created Binary Tree is: 
45 72 142 10 48 12 18 94

时间复杂度 – O(N), 其中N是链表中节点的数量。

空间复杂度 – O(N)用于创建新的二叉树。

在这里，我们遍历了链表，并为每个链表节点创建了一个新的二叉树节点。然后，我们将当前节点附加到其父节点上。程序员可以尝试将数组转换为二叉树以进行更多的练习。