如何合并两棵二叉搜索树
哪些公司问过
答案要点
- 中序遍历两棵树得到有序数组,按归并方式合并
- 由有序数组取中点递归重建,得到平衡 BST
- 中序加归并加重建:时间 O(m+n),空间 O(m+n)
- 逐个插入法平衡时 O(m log(m+n)),退化时变慢且结果可能不平衡
- 可原地转为有序双向链表合并再还原,节省额外空间
易错点
- 直接把一棵树挂到另一棵树的叶子上,破坏 BST 性质
- 忽略逐个插入在树退化时的最坏复杂度
- 没考虑两棵树中存在重复值的情况
面试官常见追问
- 只要求按升序输出两棵树所有元素呢?
- 有序数组怎么建平衡 BST?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场