面试题库 › 算法 / 大模型 › 二叉搜索树转双向链表

二叉搜索树转双向链表

难度 ★★☆在 7 场真实面经中被问到 方向:算法 / 大模型考点:树与二叉树

哪些公司问过

字节跳动3快手1Shopee1蚂蚁集团1今日头条1

常见岗位:机器学习算法(泛)、NLP / 语音、推荐搜索广告、C++ 后端、Go 后端

答案要点

  1. BST 中序遍历有序,据此构造有序的双向链表
  2. 用 pre 指针记录中序遍历的前驱节点
  3. 处理当前节点:left 指向 pre,pre.right 指向当前节点;pre 为空时当前节点是头
  4. 处理完把 pre 更新为当前节点;遍历结束 pre 就是尾节点
  5. 时间 O(n),递归栈空间 O(h);循环链表要把头尾连接

易错点

面试官常见追问

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

相关面试题