首页 > 代码库 > 算法题——二叉树转换为双向链表
算法题——二叉树转换为双向链表
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。