将链接列表结构转换为具有2个修改的二叉树结构

Question

提及可对链接列表数据结构进行2个修改，以便将其转换为二叉树数据结构？

Answer 1

这个问题相当含糊，但这是我认为可能的含义。

在链表使用的结构将有一个next指针：

struct LinkedListNode { 
    LinkedListNode *next; 
    // data element(s) 
}; 

二叉树使用将有left和right指针的结构：

struct BinaryTreeNode { 
    BinaryTreeNode *left; 
    BinaryTreeNode *right; 
    // data element(s) 
} 

所以，我猜问题涉及的两个修改可能是：

1. 的next指针更改为left指针
2. 添加right指针

Answer 2

我没有得到一点“2修改”， 而是一个LinkedList转换为BinaryTree，我们可以按照两种方法

1. 自下而上
2. 自上而下

1）自顶向下的方法：

在这种方法中，我们可以把两个LinkedList子列表和中间部分将是父节点的每个 呼吁左边和右边的子榜单递归方法。

这背后的基本逻辑就可以了，

ListToBinaryTree(LinkedList list, int start, int end) { 

    mid -> start + (end - start)/2; 
    left -> ListToBinaryTree(list, start, mid-1); 
    right -> ListToBinaryTree(list, mid+1, end); 

} 

2）自下而上的方法：

在这种方法中，我们将第一和比父元素创建子元素。

这背后的基本逻辑就可以了，

ListToBinaryTree(ListNode *& list, int start, int end) { 

    mid -> start + (end - start)/2; 
    leftChild -> ListToBinaryTree(list, start, mid-1); 
    parent -> new BinaryTree(list -> data); 
    parent -> left = leftChild; 
    list = list -> next; 
    parent -> right = ListToBinaryTree(list, mid+1, end); 

} 

希望这将是有益的。