Amazon VO 面试经验分享：BST转双向链表算法题 - Oavoservice
2025-07-09
🎤 Amazon VO 0709 辅导二面面经
👩💻 Candidate 在 Amazon VO 二面中遇到了一个经典的BST转双向链表算法题。
📋 BQ 环节
BQ1: 平时怎么快速学习知识点
- 展示学习能力和知识获取方法
- 强调实践和理论结合
- 体现持续学习的态度
BQ2: Deliver under a tight deadline
- 展示在压力下的工作能力
- 强调时间管理和优先级排序
- 体现团队协作和沟通能力
💻 Coding 环节
题目：把一个BST转为双向链表
📝 题目要求
- 将二叉搜索树转换为双向链表
- 保持BST的中序遍历顺序
- 要求空间复杂度为O(1)
❓ 问题分析
这是一个经典的树形数据结构转换问题：
- 核心思想：利用BST的中序遍历特性
- 关键点：在遍历过程中修改指针
- 挑战：O(1)空间复杂度要求
💡 思路设计
使用Morris遍历（线索化遍历）实现O(1)空间复杂度：
- 找到当前节点的前驱节点
- 将前驱节点的右指针指向当前节点
- 遍历完成后，建立双向链表的连接
💻 代码实现
class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
public class BSTToDoublyLinkedList {
// 方法1：使用Morris遍历，O(1)空间复杂度
public TreeNode bstToDoublyLinkedList(TreeNode root) {
if (root == null) return null;
TreeNode dummy = new TreeNode(0);
TreeNode prev = dummy;
TreeNode current = root;
while (current != null) {
if (current.left == null) {
// 当前节点没有左子树，直接处理
prev.right = current;
current.left = prev;
prev = current;
current = current.right;
} else {
// 找到当前节点的前驱节点
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 建立线索
predecessor.right = current;
current = current.left;
} else {
// 线索已存在，处理当前节点
predecessor.right = null;
prev.right = current;
current.left = prev;
prev = current;
current = current.right;
}
}
}
// 建立循环双向链表
TreeNode head = dummy.right;
if (head != null) {
head.left = prev;
prev.right = head;
}
return head;
}
// 方法2：递归解法，O(h)空间复杂度（h为树的高度）
private TreeNode prev = null;
private TreeNode head = null;
public TreeNode bstToDoublyLinkedListRecursive(TreeNode root) {
if (root == null) return null;
inorderTraversal(root);
// 建立循环双向链表
if (head != null) {
head.left = prev;
prev.right = head;
}
return head;
}
private void inorderTraversal(TreeNode node) {
if (node == null) return;
// 遍历左子树
inorderTraversal(node.left);
// 处理当前节点
if (prev == null) {
head = node; // 第一个节点
} else {
prev.right = node;
node.left = prev;
}
prev = node;
// 遍历右子树
inorderTraversal(node.right);
}
// 测试方法
public static void main(String[] args) {
BSTToDoublyLinkedList solution = new BSTToDoublyLinkedList();
// 构建测试BST
// 4
// / \
// 2 5
// / \
// 1 3
TreeNode root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(5);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
// 转换为双向链表
TreeNode head = solution.bstToDoublyLinkedList(root);
// 验证结果
System.out.println("双向链表（正向遍历）：");
TreeNode current = head;
do {
System.out.print(current.val + " ");
current = current.right;
} while (current != head);
System.out.println("\n双向链表（反向遍历）：");
current = head.left;
do {
System.out.print(current.val + " ");
current = current.left;
} while (current != head.left);
}
}🔍 算法分析
- 时间复杂度：O(n)，其中n是BST中的节点数
- 空间复杂度：O(1)（Morris遍历）或O(h)（递归，h为树的高度）
- 核心思想：利用Morris遍历在线性时间内完成转换
🚀 Follow-up: 如何做到空间O(1)
面试官问如何做到空间复杂度O(1)：
Morris遍历的关键步骤：
- 找前驱：对于每个节点，找到其左子树的最右节点
- 建立线索：将前驱节点的右指针指向当前节点
- 遍历：利用线索完成遍历，避免使用栈
- 清理线索：遍历完成后恢复树的结构
// Morris遍历的详细实现
public TreeNode morrisTraversal(TreeNode root) {
TreeNode current = root;
TreeNode prev = null;
TreeNode head = null;
while (current != null) {
if (current.left == null) {
// 没有左子树，处理当前节点
if (head == null) head = current;
if (prev != null) {
prev.right = current;
current.left = prev;
}
prev = current;
current = current.right;
} else {
// 有左子树，找到前驱节点
TreeNode predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 建立线索
predecessor.right = current;
current = current.left;
} else {
// 线索已存在，处理当前节点
predecessor.right = null;
if (prev != null) {
prev.right = current;
current.left = prev;
}
prev = current;
current = current.right;
}
}
}
return head;
}📊 测试用例
// 测试用例1：普通BST
// 4
// / \
// 2 5
// / \
// 1 3
// 期望输出：1 <-> 2 <-> 3 <-> 4 <-> 5
// 测试用例2：单节点
// 1
// 期望输出：1
// 测试用例3：只有右子树
// 1
// \
// 2
// \
// 3
// 期望输出：1 <-> 2 <-> 3
// 测试用例4：只有左子树
// 3
// /
// 2
// /
// 1
// 期望输出：1 <-> 2 <-> 3✨ 面试官反馈
面试官对解决方案很满意："Excellent! You've provided both the recursive solution and the Morris traversal approach. The O(1) space complexity solution is particularly impressive. You clearly understand the trade-offs between different approaches."
面试技巧分享
在 Amazon VO 面试中，除了算法实现，面试官还会关注：
1. 算法理解深度
能够理解Morris遍历的原理，并解释为什么它能实现O(1)空间复杂度。
2. 多种解法对比
提供递归和迭代两种解法，并分析它们的时间和空间复杂度。
3. 边界条件处理
考虑空树、单节点、只有左子树或右子树等特殊情况。
4. 代码实现质量
写出清晰、正确的代码，包含适当的注释和测试用例。
Oavoservice 实时辅助服务
在这次 Amazon VO 面试中，我们的实时辅助系统发挥了关键作用：
- 算法指导：帮助候选人理解Morris遍历的核心思想
- 空间优化：提供O(1)空间复杂度的实现方案
- 代码实现：协助完成完整的代码实现
- 测试验证：确保所有测试用例都能正确通过
结语
BST转双向链表是一道经典的树形数据结构题目，考察候选人对树遍历、指针操作和空间优化的理解。Morris遍历是解决这类问题的关键技巧，能够在O(1)空间复杂度下完成转换。
如果你正在准备 Amazon 或其他公司的技术面试，欢迎联系 Oavoservice。我们拥有丰富的面试经验和专业的辅助团队，能够在你最需要的时候提供及时有效的帮助。
Oavoservice - 让每一次面试都成为成功的机会！
需要辅助的同学随时dd哦，vo开始前支持mock！