首页 > 代码库 > 算法题——二叉树转换为双向链表

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

 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-tree10       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 node14       if(pLeft)15       {16             pLeft->m_pRight = pNode;17             pNode->m_pLeft = pLeft;18       }19 20       // Convert the right sub-tree21       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 node25       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 node35       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 node42       else43       {44             while(pTemp->m_pRight)45                   pTemp = pTemp->m_pRight;46       }47  48       return pTemp;49 }