Give one binary search tree, and convert it to one double-linked list
Cpp code demo as below:
1 struct BSTreeNode
2 {
3 int m_value;
4 BSTreeNode* m_pLeft;
5 BSTreeNode* m_pRight;
6 };
7
8 BSTreeNode* convert(BSTreeNode* phead, bool asRight)
9 {
10 if (!phead)
11 return NULL;
12 BSTreeNode* pLeft = 0, *pRight=0;
13 if (phead->m_pLeft)
14 pLeft = convert(phead->m_pLeft, false);
15 if (pLeft) {
16 pLeft->m_pRight = phead;
17 phead->m_pLeft = pLeft;
18 }
19 if (phead->m_pRight)
20 pRight = convert(phead->m_pRight, true);
21 if (pRight) {
22 pRight->m_pLeft = phead;
23 phead->m_pRight = pRight;
24 }
25 BSTreeNode* ptmp = phead;
26 if (asRight) {
27 while (ptmp->m_pLeft) {
28 ptmp = ptmp->m_pLeft;
29 }
30 } else {
31 while (ptmp->m_pRight) {
32 ptmp = ptmp->m_pRight;
33 }
34 }
35 return ptmp;
36 }
37
38 BSTreeNode* convert2doublelist(BSTreeNode* phead)
39 {
40 return convert(phead, true);
41 }
42