左神算法：将搜索二叉树转换成双向链表（Java版）

本题来自左神《程序员代码面试指南》“将搜索二叉树转换成双向链表”题目。

题目

对二叉树的节点来说，有本身的值域，有指向左孩子节点和右孩子节点的两个指针；对双向链表的节点来说，有本身的值域，有指向上一个节点和下一个节点的指针。在结构上，两种结构有相似性，现在有一棵搜索二叉树，请将其转换为一个有序的双向链表。

例如，节点定义为：

public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;} }

一棵搜索二叉树如图2-11 所示。

这棵搜索二叉树转换后的双向链表从头到尾依次是1～9。对每一个节点来说，原来的right指针等价于转换后的next 指针，原来的left 指针等价于转换后的last 指针，最后返回转换后的双向链表头节点。

题解

方法一

用队列等容器收集二叉树中序遍历结果的方法。时间复杂度为O(N)，额外空间复杂度为O(N)，具体过程如下：

1．生成一个队列，记为queue，按照二叉树中序遍历的顺序，将每个节点放入queue 中。
2．从queue 中依次弹出节点，并按照弹出的顺序重连所有的节点即可。

方法一的具体实现请参看如下代码中的convert1 方法。

/*** 方法1：二叉树中序遍历* @param head* @return*/ public static Node convert1(Node head) {Queue<Node> queue = new LinkedList<Node>();inOrderToQueue(head, queue); // 中序遍历，结果存在 queue 中if (queue.isEmpty()) {return head;}head = queue.poll(); // 头结点Node pre = head;pre.left = null;Node cur = null;while (!queue.isEmpty()) { // 逐一出队，并逐个连接，得到一个链表cur = queue.poll();pre.right = cur;cur.left = pre;pre = cur;}pre.right = null;return head; }public static void inOrderToQueue(Node head, Queue<Node> queue) {if (head == null) {return;}inOrderToQueue(head.left, queue); // 递归遍历左子树中的节点，加入队列中queue.offer(head); // 将根节点加入队列中inOrderToQueue(head.right, queue); // 递归遍历右子树中的节点，加入队列中 }

方法二

利用递归函数，除此之外，不使用任何容器的方法。时间复杂度为O(N)，额外空间复杂度为O(h)，h 为二叉树的高度。

实现递归函数process。process 的输入参数是一棵二叉树的头节点X，功能是将以X 为头的搜索二叉树转换为一个有序双向链表。返回值是这个有序双向链表的头节点和尾节点，所以返回值的类型是一个复杂结构，就是如下的RetrunType 类。

public static class RetrunType {public Node start;public Node end;public RetrunType(Node start, Node end) {this.start = start;this.end = end;} }

具体过程为：

• 先把以 X 为头的搜索二叉树的左子树转换为有序双向链表，并且返回左子树有序双向链表的头和尾
• 然后把 以X 为头的搜索二叉树的右子树转换为有序双向链表，并且返回右子树有序双向链表的头和尾
• 接着通过X 把两部分接起来即可
• 最后不要忘记，递归函数对任何节点的要求是一样的，所以要返回此时大的有序双向链表的头和尾。具体实现请参看如下代码中的convert2 方法。

完整代码（含测试用例）

package chapter_2_listproblem;import java.util.LinkedList; import java.util.Queue;public class Problem_15_BSTtoDoubleLinkedList {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}/*** 方法1：二叉树中序遍历* @param head* @return*/public static Node convert1(Node head) {Queue<Node> queue = new LinkedList<Node>();inOrderToQueue(head, queue); // 中序遍历，结果存在 queue 中if (queue.isEmpty()) {return head;}head = queue.poll(); // 头结点Node pre = head;pre.left = null;Node cur = null;while (!queue.isEmpty()) { // 逐一出队，并逐个连接，得到一个链表cur = queue.poll();pre.right = cur;cur.left = pre;pre = cur;}pre.right = null;return head;}public static void inOrderToQueue(Node head, Queue<Node> queue) {if (head == null) {return;}inOrderToQueue(head.left, queue); // 递归遍历左子树中的节点，加入队列中queue.offer(head); // 将根节点加入队列中inOrderToQueue(head.right, queue); // 递归遍历右子树中的节点，加入队列中}public static class ReturnType {public Node start; // 链表头public Node end; // 链表尾public ReturnType(Node start, Node end) {this.start = start;this.end = end;}}/*** 方法2：用递归实现将BSTree转化为有序双向链表*/public static Node convert2(Node head) {if (head == null) {return null;}return process(head).start;}public static ReturnType process(Node head) {if (head == null) {return new ReturnType(null, null);}ReturnType leftList = process(head.left); // 左子树转换为有序双向链表，返回左子树有序双向链表的头和尾ReturnType rightList = process(head.right); // 右子树转化为有序双向链表，返回右子树有序双向链表的头和尾// 通过将根节点放在中间，把得到的左右两个双向链表连起来if (leftList.end != null) {leftList.end.right = head;}head.left = leftList.end;head.right = rightList.start;if (rightList.start != null) {rightList.start.left = head;}// 返回连接好的双向链表的头和尾return new ReturnType(leftList.start != null ? leftList.start : head,rightList.end != null ? rightList.end : head);}/*** BSTree的中序遍历输出*/public static void printBSTInOrder(Node head) {System.out.print("BST in-order: ");if (head != null) {inOrderPrint(head);}System.out.println();}public static void inOrderPrint(Node head) {if (head == null) {return;}inOrderPrint(head.left);System.out.print(head.value + " ");inOrderPrint(head.right);}public static void printDoubleLinkedList(Node head) {System.out.print("Double Linked List: ");Node end = null;while (head != null) {System.out.print(head.value + " ");end = head;head = head.right;}System.out.print("| ");while (end != null) {System.out.print(end.value + " ");end = end.left;}System.out.println();}// for testpublic static void main(String[] args) {Node head = new Node(5);head.left = new Node(2);head.right = new Node(9);head.left.left = new Node(1);head.left.right = new Node(3);head.left.right.right = new Node(4);head.right.left = new Node(7);head.right.right = new Node(10);head.left.left = new Node(1);head.right.left.left = new Node(6);head.right.left.right = new Node(8);printBSTInOrder(head);head = convert1(head);printDoubleLinkedList(head);head = new Node(5);head.left = new Node(2);head.right = new Node(9);head.left.left = new Node(1);head.left.right = new Node(3);head.left.right.right = new Node(4);head.right.left = new Node(7);head.right.right = new Node(10);head.left.left = new Node(1);head.right.left.left = new Node(6);head.right.left.right = new Node(8);printBSTInOrder(head);head = convert2(head);printDoubleLinkedList(head);} }

关于方法二中时间复杂度与空间复杂度的解释，可以用process 递归函数发生的次数来估算时间复杂度，process 会处理所有的子树，子树的数量就是二叉树节点的个数。所以时间复杂度为O(N)，process 递归函数最多占用二叉树高度为h 的栈空间，所以额外空间复杂度为O(h)。

拓展

本题在复杂度方面能够达到的程度完全取决于二叉树遍历的实现，如果一颗二叉树遍历的实现在时间和空间复杂度上足够好，那么本题在时间复杂度和空间复杂度上就同样好。有没有时间复杂度为O(N)、额外空间复杂度为O(1)的遍历实现呢？也就是既不用栈，也不用递归函数，只用有限几个变量的实现？有。有兴趣的读者可阅读本书“遍历二叉树的神级方法”问题，然后结合神级的遍历方法（线索二叉树）重新实现这道题。有关方法二中递归函数的设计方法，我们在本书的二叉树章节还能进一步学习并形成固定的套路。

总结

以上是生活随笔为你收集整理的左神算法：将搜索二叉树转换成双向链表（Java版）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。