本題來自左神《程序員代碼面試指南》“將搜索二叉樹轉(zhuǎn)換成雙向鏈表”題目。

題目

對二叉樹的節(jié)點來說，有本身的值域，有指向左孩子節(jié)點和右孩子節(jié)點的兩個指針；對雙向鏈表的節(jié)點來說，有本身的值域，有指向上一個節(jié)點和下一個節(jié)點的指針。在結(jié)構(gòu)上，兩種結(jié)構(gòu)有相似性，現(xiàn)在有一棵搜索二叉樹，請將其轉(zhuǎn)換為一個有序的雙向鏈表。

例如，節(jié)點定義為：

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

一棵搜索二叉樹如圖2-11 所示。

這棵搜索二叉樹轉(zhuǎn)換后的雙向鏈表從頭到尾依次是1～9。對每一個節(jié)點來說，原來的right指針等價于轉(zhuǎn)換后的next 指針，原來的left 指針等價于轉(zhuǎn)換后的last 指針，最后返回轉(zhuǎn)換后的雙向鏈表頭節(jié)點。

題解

方法一

用隊列等容器收集二叉樹中序遍歷結(jié)果的方法。時間復雜度為O(N)，額外空間復雜度為O(N)，具體過程如下：

1．生成一個隊列，記為queue，按照二叉樹中序遍歷的順序，將每個節(jié)點放入queue 中。
2．從queue 中依次彈出節(jié)點，并按照彈出的順序重連所有的節(jié)點即可。

方法一的具體實現(xiàn)請參看如下代碼中的convert1 方法。

/*** 方法1：二叉樹中序遍歷* @param head* @return*/ public static Node convert1(Node head) {Queue<Node> queue = new LinkedList<Node>();inOrderToQueue(head, queue); // 中序遍歷，結(jié)果存在 queue 中if (queue.isEmpty()) {return head;}head = queue.poll(); // 頭結(jié)點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); // 遞歸遍歷左子樹中的節(jié)點，加入隊列中queue.offer(head); // 將根節(jié)點加入隊列中inOrderToQueue(head.right, queue); // 遞歸遍歷右子樹中的節(jié)點，加入隊列中 }

方法二

利用遞歸函數(shù)，除此之外，不使用任何容器的方法。時間復雜度為O(N)，額外空間復雜度為O(h)，h 為二叉樹的高度。

實現(xiàn)遞歸函數(shù)process。process 的輸入?yún)?shù)是一棵二叉樹的頭節(jié)點X，功能是將以X 為頭的搜索二叉樹轉(zhuǎn)換為一個有序雙向鏈表。返回值是這個有序雙向鏈表的頭節(jié)點和尾節(jié)點，所以返回值的類型是一個復雜結(jié)構(gòu)，就是如下的RetrunType 類。

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

具體過程為：

• 先把以 X 為頭的搜索二叉樹的左子樹轉(zhuǎn)換為有序雙向鏈表，并且返回左子樹有序雙向鏈表的頭和尾
• 然后把 以X 為頭的搜索二叉樹的右子樹轉(zhuǎn)換為有序雙向鏈表，并且返回右子樹有序雙向鏈表的頭和尾
• 接著通過X 把兩部分接起來即可
• 最后不要忘記，遞歸函數(shù)對任何節(jié)點的要求是一樣的，所以要返回此時大的有序雙向鏈表的頭和尾。具體實現(xiàn)請參看如下代碼中的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); // 中序遍歷，結(jié)果存在 queue 中if (queue.isEmpty()) {return head;}head = queue.poll(); // 頭結(jié)點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); // 遞歸遍歷左子樹中的節(jié)點，加入隊列中queue.offer(head); // 將根節(jié)點加入隊列中inOrderToQueue(head.right, queue); // 遞歸遍歷右子樹中的節(jié)點，加入隊列中}public static class ReturnType {public Node start; // 鏈表頭public Node end; // 鏈表尾public ReturnType(Node start, Node end) {this.start = start;this.end = end;}}/*** 方法2：用遞歸實現(xiàn)將BSTree轉(zhuǎn)化為有序雙向鏈表*/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); // 左子樹轉(zhuǎn)換為有序雙向鏈表，返回左子樹有序雙向鏈表的頭和尾ReturnType rightList = process(head.right); // 右子樹轉(zhuǎn)化為有序雙向鏈表，返回右子樹有序雙向鏈表的頭和尾// 通過將根節(jié)點放在中間，把得到的左右兩個雙向鏈表連起來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);} }

關(guān)于方法二中時間復雜度與空間復雜度的解釋，可以用process 遞歸函數(shù)發(fā)生的次數(shù)來估算時間復雜度，process 會處理所有的子樹，子樹的數(shù)量就是二叉樹節(jié)點的個數(shù)。所以時間復雜度為O(N)，process 遞歸函數(shù)最多占用二叉樹高度為h 的棧空間，所以額外空間復雜度為O(h)。

拓展

本題在復雜度方面能夠達到的程度完全取決于二叉樹遍歷的實現(xiàn)，如果一顆二叉樹遍歷的實現(xiàn)在時間和空間復雜度上足夠好，那么本題在時間復雜度和空間復雜度上就同樣好。有沒有時間復雜度為O(N)、額外空間復雜度為O(1)的遍歷實現(xiàn)呢？也就是既不用棧，也不用遞歸函數(shù)，只用有限幾個變量的實現(xiàn)？有。有興趣的讀者可閱讀本書“遍歷二叉樹的神級方法”問題，然后結(jié)合神級的遍歷方法（線索二叉樹）重新實現(xiàn)這道題。有關(guān)方法二中遞歸函數(shù)的設(shè)計方法，我們在本書的二叉樹章節(jié)還能進一步學習并形成固定的套路。

總結(jié)

以上是生活随笔為你收集整理的左神算法：将搜索二叉树转换成双向链表（Java版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。