剑指offer26：将二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

1 题目描述

　　输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

2 思路和方法

　　在二叉搜索树中，每个结点都有两个分别指向其左、右子树的指针，左子树结点的值总是小于父结点的值，右子树结点的值总是大于父结点的值。

　　在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。

　　所以这两种数据结构的结点是一致，二叉搜索树和双向链表，只是因为两个指针的指向不同而已举个例子，如下图中的二叉搜索树，转换后的双向链表为：

　　思路：

　　为了减少指针的变换次数，并让操作更加简单，在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向下一个结点的指针。
由于要求链表是有序的，可以借助二叉树中序遍历，因为中序遍历算法的特点就是从小到大访问结点。当遍历访问到根结点时，假设根结点的左侧已经处理好，只需将根结点与上次访问的最近结点（左子树中最大值结点）的指针连接好即可。进而更新当前链表的最后一个结点指针。

　　方法：

　　如上图的二叉排序树，就分成了根结点10、以结点6为根的左子对和以结点14为根的右子树。从变换的链表中我们可以看到，应当把结点10的left指针指向结点8，把结点8的right指针指向结点10，而由于我们采用的是中序遍历，所以当我们遍历到结点10时，结点10的左子树已经转化为一个有序的双向链表，而结点8是这个已经转化的双向链表的尾结点，所以我们应该用一个变量last_node来保存最后一个结点的指针，以便在与根结点连续时使用。然后把这个变量last_node的值更新为指向根结点10。对于结点10的右子树，采取相似的操作。

3 C++核心代码

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 public:
12     TreeNode* Convert(TreeNode* pRootOfTree)
13     {
14         stack<TreeNode*> st;
15         TreeNode *cur = pRootOfTree;     //为临时节点用来遍历树的节点，初始值为根节点root
16         TreeNode *pre = pRootOfTree;    // 用于保存中序遍历序列的上一节点
17         TreeNode *head = pRootOfTree;    //用于记录双向链表的头结点
18         bool isFirst = true;         //判断是否为左子树链表的第一个节点
19         while(cur||!st.empty())
20         {
21             while(cur)
22             {
23                 st.push(cur);
24                 cur = cur->left;
25             }
26             cur = st.top();    //此时的cur为左子树最左边的节点
27             st.pop();
28             if(isFirst)    //假如是左子树链表的第一个节点
29             {   //将cur赋值给root节点
30                 head = pre = cur;    //将中序遍历序列中的第一个节点记为根节点(root node)
31                 isFirst = false;
32             }
33             else
34             {
35                 pre->right = cur;
36                 cur->left = pre;
37                 pre = cur;
38             }
39             cur = cur->right;
40         }
41         return head;
42     }
43 };

View Code

4 C++完整代码

  1 #include<iostream>
  2 using namespace std;
  3 
  4 //二叉树结点定义
  5 struct BinaryTreeNode
  6 {
  7     int Value;
  8     BinaryTreeNode* Left;
  9     BinaryTreeNode* Right;
 10 };
 11 
 12 //创建二叉树结点
 13 BinaryTreeNode* CreateBinaryTreeNode(int value)
 14 {
 15     BinaryTreeNode* pNode = new BinaryTreeNode();
 16     pNode->Value = value;
 17     pNode->Left = NULL;
 18     pNode->Right = NULL;
 19     return pNode;
 20 }
 21 
 22 //连接树结点
 23 void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
 24 {
 25     if (pParent != NULL)
 26     {
 27         pParent->Left = pLeft;
 28         pParent->Right = pRight;
 29     }
 30 }
 31 
 32 //中序遍历
 33 void InOrderPrintTree(BinaryTreeNode* pRoot)
 34 {
 35     if (pRoot != NULL)
 36     {
 37         //遍历左边
 38         if (pRoot->Left != NULL)
 39         {
 40             InOrderPrintTree(pRoot->Left);
 41         }
 42         //根
 43         cout << "value of this node is " << pRoot->Value << endl;
 44         //遍历右边
 45         if (pRoot->Right != NULL)
 46         {
 47             InOrderPrintTree(pRoot->Right);
 48         }
 49 
 50     }
 51     else
 52     {
 53         cout << "this node is null." << endl;
 54     }
 55 
 56 }
 57 
 58 //转换排序二叉树为双向链表
 59 void Convert(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeLnList)
 60 {
 61     if (pNode == NULL)
 62     {
 63         return;
 64     }
 65 
 66     BinaryTreeNode* pCurrent = pNode;
 67 
 68     //左子树转换，遍历到左子树的叶子结点
 69     if (pCurrent->Left != NULL)
 70     {
 71         Convert(pCurrent->Left, pLastNodeLnList);
 72     }
 73     pCurrent->Left = *pLastNodeLnList;
 74     if ((*pLastNodeLnList) != NULL)
 75     {
 76         (*pLastNodeLnList)->Right = pCurrent;
 77     }
 78     *pLastNodeLnList = pCurrent;
 79 
 80     //右子树转换
 81     if (pCurrent->Right != NULL)
 82     {
 83         Convert(pCurrent->Right, pLastNodeLnList);
 84     }
 85 
 86 }
 87 
 88 //获取双向链表头结点
 89 BinaryTreeNode* Convert(BinaryTreeNode* pRoot)
 90 {
 91     //指向双向链表的尾结点
 92     BinaryTreeNode* pLastNodeInList = NULL;
 93     //转换排序二叉树为双向链表
 94     Convert(pRoot, &pLastNodeInList);
 95 
 96     //求双向链表的头结点
 97     BinaryTreeNode* pHeadOfList = pLastNodeInList;
 98     while (pHeadOfList != NULL&&pHeadOfList->Left != NULL)
 99     {
100         pHeadOfList = pHeadOfList->Left;
101     }
102     return pHeadOfList;
103 }
104 
105 //打印双向链表
106 void PrintList(BinaryTreeNode* pRoot)
107 {
108     BinaryTreeNode* pNode = pRoot;
109 
110     while (pNode != NULL)
111     {
112         cout << pNode->Value << "    ";
113         pNode = pNode->Right;
114     }
115 
116     cout << endl;
117     cout << "PrintList ends." << endl << endl;
118 
119 }
120 
121 
122 // ====================测试代码====================
123 void Test1()
124 {
125     //                 10
126     //              /      
127     //            6        14
128     //           /        /  
129     //          4  8      12  16
130 
131     cout << "The Test1:" << endl;
132 
133     //创建树结点
134     BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
135     BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
136     BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14);
137     BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
138     BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
139     BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
140     BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16);
141 
142     //连接树结点
143     ConnectTreeNodes(pNode10, pNode6, pNode14);
144     ConnectTreeNodes(pNode6, pNode4, pNode8);
145     ConnectTreeNodes(pNode14, pNode12, pNode16);
146 
147     //中序遍历
148     InOrderPrintTree(pNode10);
149     //获取双向链表头结点
150     BinaryTreeNode* pHeadOfList = Convert(pNode10);
151     //输出链表
152     PrintList(pHeadOfList);
153 
154 }
155 
156 void Test2()
157 {
158     //               5
159     //              /
160     //             4
161     //            /
162     //           3
163     //          /
164     //         2
165     //        /
166     //       1
167 
168     cout << "The Test2:" << endl;
169     //创建树结点
170     BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
171     BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
172     BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
173     BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
174     BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
175 
176     //连接树结点
177     ConnectTreeNodes(pNode5, pNode4, NULL);
178     ConnectTreeNodes(pNode4, pNode3, NULL);
179     ConnectTreeNodes(pNode3, pNode2, NULL);
180     ConnectTreeNodes(pNode2, pNode1, NULL);
181 
182     //中序遍历
183     InOrderPrintTree(pNode5);
184     //获取双向链表头结点
185     BinaryTreeNode* pHeadOfList = Convert(pNode5);
186     //输出链表
187     PrintList(pHeadOfList);
188 
189 }
190 
191 void Test3()
192 {
193     // 1
194     //  
195     //   2
196     //    
197     //     3
198     //      
199     //       4
200     //        
201     //         5
202 
203     cout << "The Test3:" << endl;
204     //创建树结点
205     BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
206     BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);
207     BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);
208     BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
209     BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
210 
211     //连接树结点
212     ConnectTreeNodes(pNode1, NULL, pNode2);
213     ConnectTreeNodes(pNode2, NULL, pNode3);
214     ConnectTreeNodes(pNode3, NULL, pNode4);
215     ConnectTreeNodes(pNode4, NULL, pNode5);
216 
217     //中序遍历
218     InOrderPrintTree(pNode1);
219     //获取双向链表头结点
220     BinaryTreeNode* pHeadOfList = Convert(pNode1);
221     //输出链表
222     PrintList(pHeadOfList);
223 
224 }
225 
226 void Test4()
227 {
228     // 树中只有1个结点
229 
230     cout << "The Test4:" << endl;
231     //创建树结点
232     BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);
233 
234     //连接树结点
235     ConnectTreeNodes(pNode1, NULL, NULL);
236 
237     //中序遍历
238     InOrderPrintTree(pNode1);
239     //获取双向链表头结点
240     BinaryTreeNode* pHeadOfList = Convert(pNode1);
241     //输出链表
242     PrintList(pHeadOfList);
243 
244 }
245 
246 void Test5()
247 {
248     // 树中没有结点
249 
250     cout << "The Test5:" << endl;
251     //创建树结点
252     BinaryTreeNode* pNode1 = CreateBinaryTreeNode(NULL);
253 
254     //连接树结点
255     ConnectTreeNodes(pNode1, NULL, NULL);
256 
257     //中序遍历
258     InOrderPrintTree(pNode1);
259     //获取双向链表头结点
260     BinaryTreeNode* pHeadOfList = Convert(pNode1);
261     //输出链表
262     PrintList(pHeadOfList);
263 
264 }
265 
266 void main()
267 {
268     Test1();
269     Test2();
270     Test3();
271     Test4();
272     Test5();
273     system("pause");
274 }

View Code

参考资料

https://blog.csdn.net/u012477435/article/details/83351659

https://blog.csdn.net/yanxiaolx/article/details/52073221

https://blog.csdn.net/jyy305/article/details/76383723（Solution中函数不同时）

https://blog.csdn.net/ljianhui/article/details/22338405（完整代码另一个版本）