"常见程序员面试题精选100题1：如何将二元查找树转换为排序的双向链表"

常见：程序员面试题精选100题 前言 随着高校的持续扩张，每年应届毕业生的数目都在不断增长，伴随而来的是应届毕业生的就业压力也越来越大。在这样的背景下，就业变成一个买方市场的趋势越来越明显。为了找到一个称心的工作，绝大多数应届毕业生都必须反复经历简历筛选、电话面试、笔试、面试等环节。在这些环节中，面试无疑起到最为重要的作用，因为通过面试公司能够最直观地了解学生的能力。 为了有效地准备面试，面经这个新兴概念应运而生。笔者在当初找工作阶段也从面经中获益匪浅并最终找到满意的工作。为了方便后来者，笔者花费大量时间收集并整理散落在茫茫网络中的面经。不同行业的面经全然不同，笔者从自身专业出发，着重关注程序员面试的面经，并从精选出若干具有代表性的技术类的面试题展开讨论，希望能给读者带来一些启发。 由于笔者水平有限，给各面试题提供的思路和代码难免会有错误，还请读者批评指正。另外，热忱欢迎读者能够提供更多、更好的面试题，本人将感激不尽。 (01)把二元查找树转变成排序的双向链表 题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 分析：首先，我们可以利用二叉查找树的性质来确定中序遍历的顺序，即从小到大。然后，我们可以利用中序遍历的顺序来调整指针的指向，使其形成排序的双向链表。 具体实现如下： 1. 定义一个全局变量pre，用来记录当前节点的前一个节点。 2. 编写一个递归函数，用来实现中序遍历。 - 如果当前节点为空，则返回。 - 递归遍历当前节点的左子树。 - 如果pre为空，表示当前节点为双向链表的头节点，将pre指向该节点。 - 如果pre不为空，将pre的右指针指向当前节点，当前节点的左指针指向pre。 - 更新pre为当前节点。 - 递归遍历当前节点的右子树。 3. 在主函数中，调用中序遍历函数并返回链表的头节点。 实例代码如下： ```python class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right pre = None def convert(root): global pre def inorder(node): if node is None: return inorder(node.left) if pre is None: pre = node else: pre.right = node node.left = pre pre = node inorder(node.right) inorder(root) return pre # 测试 root = TreeNode(4) root.left = TreeNode(2) root.left.left = TreeNode(1) root.left.right = TreeNode(3) root.right = TreeNode(5) head = convert(root) # 打印链表 current = head while current: print(current.val) current = current.right ``` 以上是将二叉查找树转变成排序的双向链表的实现方法。通过使用中序遍历和指针的调整，即可得到题目所要求的结果。 希望本文对于各位准备面试的程序员们能够起到一定的帮助和指导作用，希望大家都能顺利找到自己满意的工作。如果有任何问题或建议，欢迎与我交流。