算法题——二叉树转换为双向链表

 1 BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
 2 {
 3       if(!pNode)
 4             return NULL;
 5 
 6       BSTreeNode *pLeft = NULL;
 7       BSTreeNode *pRight = NULL;
 8 
 9       // Convert the left sub-tree
10       if(pNode->m_pLeft)
11             pLeft = ConvertNode(pNode->m_pLeft, false);
12 
13       // Connect the greatest node in the left sub-tree to the current node
14       if(pLeft)
15       {
16             pLeft->m_pRight = pNode;
17             pNode->m_pLeft = pLeft;
18       }
19 
20       // Convert the right sub-tree
21       if(pNode->m_pRight)
22             pRight = ConvertNode(pNode->m_pRight, true);
23 
24       // Connect the least node in the right sub-tree to the current node
25       if(pRight)
26       {
27             pNode->m_pRight = pRight;
28             pRight->m_pLeft = pNode;
29       }
30 
31       BSTreeNode *pTemp = pNode;
32 
33       // If the current node is the right child of its parent, 
34       // return the least node in the tree whose root is the current node
35       if(asRight)
36       {
37             while(pTemp->m_pLeft)
38                   pTemp = pTemp->m_pLeft;
39       }
40       // If the current node is the left child of its parent, 
41       // return the greatest node in the tree whose root is the current node
42       else
43       {
44             while(pTemp->m_pRight)
45                   pTemp = pTemp->m_pRight;
46       }
47  
48       return pTemp;
49 }