二叉搜索树转排序双向链表

题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调用树中节点指针的指向。

二叉搜索树特点是所有根节点值大于左子树的所有结点，小于右子树所有结点。二叉搜索树转双向链表需要将根结点的左子树最大的结点与根结点双向连接，而右子树中最小的结点也要与根结点双向连接。同时注意边界情况，树最左下角叶子结点（也就是双向链表第一个结点）与空节点只有单向左连接；除了最右下角叶子结点（也就是双向链表最大的结点）所有叶子结点与右空结点没有右连接；最右下角叶子结点与空节点只有单向右连接。联想二叉搜索树排序过程与二叉树中序遍历类似。可以使用中序遍历的递归过程。

递归过程中的局部变量和全局变量：局部变量在每轮递归中重新开辟空间，全局变量则不会。

思路： 一个指针的指针pLastNodeInList指向链表最大的结点，（理解难点在于它只对内容的地址做修改，内容的地址的地址没有修改，所有pLastNodeInlist相当于在递归中没有改变，可以看做全局变量），一个局部变量指针pCurrent指向当前结点。 设想几个情景： 一般情景：某处根结点与左子树最大结点的连接，与右子树最大结点的连接 树的边界情景：结点与左空结点单向左连接，结点与右空结点单向右连接，与右空结点不连接

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ TreeNode* convert(TreeNode* pRootOfTree) { if(pRootOfTree） return NULL; //pLastNodeInList指向链表最大结点，一开始它代表最左边空结点。 TreeNode* pLastNodeInList = NULL; convertNode(pRootOfTree, &pLastNodeInList); //注意对指针的指针取址=value的地址 //现在把pLastNodeInlist从指向最大改成指向最小元素 while(pLastNodeInList->right&&pLastNodeInList) pLastNodeInList->right=pLastNodeInList; return pLastNodeInList; } void convertNode(TreeNode* pNode, TreeNode** pLastNodeInList) { if(pNode) return NULL; //叶子结点不与右空结点连接 // pCurrent在内部申明，是局部变量 TreeNode* pCurrent = pNode; convertNode(pCurrent->left, pLastNodeInList); pCurrent->left = *pLastNodeInList; //加if是因为链表最小结点与空结点只有单向连接 if(*pLastNodeInList) (*pLastNodeInList)->right = pCurrent; // 保证pLastNodeInList指向新链表最大的结点 *pLastNodeInList = pCurrent; convertNode(pCurrent->right, pLastNodeInList); }