【IT笔试面试题整理】二叉搜索树转换为双向链表

【试题描述】将二叉搜索树转换为双向链表

对于二叉搜索树，可以将其转换为双向链表，其中，节点的左子树指针在链表中指向前一个节点，右子树指针在链表中指向后一个节点。

思路一：

采用递归思想，对于二叉搜索树，将左、右子树分别转换为双向链表，左子树转换所得链表的头结点即整个树的头结点，左子树转换所得链表的尾节点与根节点相邻；右子树转换所得链表的尾节点即整个树的尾节点，右子树转换所得链表的头结点与根节点相邻。

 1     private static Node last;
 2     public static Node treeToList(Node tree)
 3     {
 4         Node head;
 5         // 若树为空，返回空
 6         if (tree == null)
 7             return null;
 8 
 9         // 若无左子树，则该根节点为链表的头结点
10         if (tree.left == null)
11             head = tree;
12         // 若有左子树，递归调用转换函数将左子树转换为双向链表
13         // 左子树转换所得链表的头结点是整个树的头结点
14         // 左子树链表的尾结点与根节点相邻
15         else
16         {
17             head = treeToList(tree.left);
18             tree.left = last;
19             last.right = tree;
20         }
21         //若无右子树，则该根节点为链表的尾结点 
22         if (tree.right == null)
23             last = tree;
24         //若有右子树，递归调用转换函数将右子树转换为双向链表 
25         //右子树转换所得链表的尾结点是整个树的尾结点 
26         //右子树链表的头结点与根节点相邻 
27         else
28         {
29             tree.right = treeToList(tree.right);
30             tree.right.left = tree;
31         }
32         return head;
33 
34     }

思路二：

我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

 1     // /////////////////////////////////////////////////////////////////////
 2     // Covert a sub binary-search-tree into a sorted double-linked list
 3     // Input: pNode - the head of the sub tree
 4     // pLast - the tail of the double-linked list
 5     // /////////////////////////////////////////////////////////////////////
 6     private static Node pLast;
 7 
 8     public static void treeToList(Node pNode)
 9     {
10         if (pNode == null)
11             return;
12         Node pCurrent = pNode;
13 
14         // Convert the left sub-tree
15         if (pCurrent.left != null)
16             treeToList(pCurrent.left);
17 
18         // Put the current node into the double-linked list
19         pCurrent.left = pLast;
20 
21         if (pLast != null)
22             pLast.right = pCurrent;
23 
24         pLast = pCurrent;
25         // Convert the right sub-tree
26         if (pCurrent.right != null)
27             treeToList(pCurrent.right);
28     }
29 
30     // /////////////////////////////////////////////////////////////////////
31     // Covert a binary search tree into a sorted double-linked list
32     // Input: pHead - the head of tree
33     // Output: the head of sorted double-linked list
34     // /////////////////////////////////////////////////////////////////////
35     public static Node convertTree(Node root)
36     {
37         treeToList(root);
38 
39         // Get the head of the double-linked list
40         Node pHead = pLast;
41         while (pHead != null && pHead.left != null)
42             pHead = pHead.left;
43 
44         return pHead;
45 
46     }