java - 从已排序的双向链表创建二叉搜索树

Question

嘿伙计们，我正在研究编程面试问题，但我陷入了这个问题。

我正在尝试递归地执行此操作，但我不知道从哪里开始。

这是我迄今为止的算法:

 makeTree(head, tail){
   nodeMid = list/2
   root = nodeMid
   root.left = makeTree(head, nodeMid)
   root.right = makeTree(nodeMid, tail)

我的想法正确吗？任何意见都将受到高度赞赏。谢谢!

Answer 1

以下是一些要点:

1. 获取链表的中间部分并将其设为根。

2. 对左半部分和右半部分递归地执行相同的操作。

   • 获取左半部分的中间部分并将其设为根的左子节点 在第 1 步中创建。

   • 获取右半部分的中间部分，并将其设为右 child 在步骤 1 中创建的根目录。

时间复杂度:O(nLogn)，其中n是链表中的节点数。