题目来源“数据结构与算法面试题80道”。
问题分析：二叉查找树是一种二叉树的结构，其中，根节点的值大于左子树的值，小于右子树的值。而二叉查找树的中序遍历即为排序的结果。对于根节点，前驱指针指向左子树中最大的节点，同理，后驱指针指向右子树中最小的节点，如下图所示：
树是一种递归的结果，因此，对于左右子树，也需要执行相同的操作。
方法：
代码语言：javascript复制BSTreeNode* convert(BSTreeNode *root){
if (NULL == root ||
(NULL == root->m_pLeft && NULL == root->m_pRight)){
return root;
}
convert(root->m_pLeft);
BSTreeNode* p_left = root->m_pLeft;
while(p_left->m_pRight != NULL){
p_left = p_left->m_pRight;
}
root->m_pLeft = p_left;
p_left->m_pRight = root;
convert(root->m_pRight);
BSTreeNode* p_right = root->m_pRight;
while(p_right->m_pLeft != NULL){
p_right = p_right->m_pLeft;
}
root->m_pRight = p_right;
p_right->m_pLeft = root;
BSTreeNode *p = root;
while (NULL != p->m_pLeft){
p = p->m_pLeft;
}
return p;
}
