面试题库 › Java 后端 › 升序数组或链表转换为平衡二叉搜索树

升序数组或链表转换为平衡二叉搜索树

难度 ★★☆在 3 场真实面经中被问到 方向:Java 后端考点:树与二叉树

哪些公司问过

小米1微软1携程1

常见岗位:Java 后端

答案要点

  1. 升序序列即 BST 的中序遍历,每次取中间元素为根保证平衡
  2. 数组:递归区间 [l, r] 取 mid,时间 O(n),栈 O(log n)
  3. 链表:快慢指针找中点为根,断开前驱的 next,左右递归,O(n log n)
  4. 优化:先求长度,按中序顺序递归建树,链表指针顺序后移,O(n)
  5. 递归终止:区间为空或链表段为空时返回空节点

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题