推荐订阅源

This is a question from Microsoft, in general, recurtion is first tip on binary tree.
Convert a Binary search tree to double linked list, and no new point, only change pointer.
for example:
                    10
                   /    \
                6      14
               /  \     /   \
            4    8   12 16                to            4=6=8=10=12=14=16

solution 1:
    now, we reach current node, first of all, we need adjust left tree to double link, and adjust the right tree. connect the two double link with current node.
//node
struct BSTreeNode {
    int          m_nValue; // value of node
  BSTreeNode *m_pLeft; // left child of node
  BSTreeNode *m_pRight; // right child of node
}

///////////////////////////////////////////////////////////////////////
// Covert a sub binary-search-tree into a sorted double-linked list
// Input: pNode - the head of the sub tree
//        asRight - whether pNode is the right child of its parent
// Output: if asRight is true, return the least node in the sub-tree
//         else return the greatest node in the sub-tree
///////////////////////////////////////////////////////////////////////
BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)
{
      if(!pNode)
            return NULL;

      BSTreeNode *pLeft = NULL;
      BSTreeNode *pRight = NULL;      // Convert the left sub-tree
      if(pNode->m_pLeft)
            pLeft = ConvertNode(pNode->m_pLeft, false);      // Connect the greatest node in the left sub-tree to the current node
      if(pLeft)
      {
            pLeft->m_pRight = pNode;
            pNode->m_pLeft = pLeft;
      }

      // Convert the right sub-tree
      if(pNode->m_pRight)
            pRight = ConvertNode(pNode->m_pRight, true);

      // Connect the least node in the right sub-tree to the current node
      if(pRight)
      {
            pNode->m_pRight = pRight;
            pRight->m_pLeft = pNode;
      }      BSTreeNode *pTemp = pNode;

      // If the current node is the right child of its parent, 
      // return the least node in the tree whose root is the current node
      if(asRight)
      {
            while(pTemp->m_pLeft)
                  pTemp = pTemp->m_pLeft;
      }
      // If the current node is the left child of its parent, 
      // return the greatest node in the tree whose root is the current node
      else
      {
            while(pTemp->m_pRight)
                  pTemp = pTemp->m_pRight;
      }
 
      return pTemp;
}