后端岗位面试题更新 2026-08-05

请将一棵二叉搜索树转换为有序双向链表,要求时间复杂度 O(n)、空间复杂度 O(1),并说明思路与实现要点。

喜马拉雅后端开发互联网/IT编码实现问题拆解技术原理

考察说明

考察二叉搜索树中序遍历与原地链表转换的算法实现能力

回答思路

  1. 明确中序遍历保证有序性
  2. 利用节点左右指针作为链表前驱后继,避免额外空间
  3. 递归或迭代实现均需确保 O(1) 额外空间(排除递归栈)
  4. 处理头尾节点连接,循环链表或首尾相接需清晰说明