通过两次修改将链表结构转换为二叉树结构

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);
}

希望这会有用。