将二叉搜索树转换为排序双链表

 1 class Solution {
 2 public:
 3     TreeNode *head=NULL,*prev=NULL;
 4     TreeNode* Convert(TreeNode* root)
 5     {
 6         if(root == NULL) return NULL;
 7         if(root->left == NULL && head == NULL) head=prev=root;//满足这个条件的一定是最左下角的叶子节点或根节点，作为排序链表的头部，此后head固定
 8         Convert(root->left);                                    //转换左子树
 9         if(prev != root) 　　　　　　　　　　　　　　　　　　　　　　　　//prev记录了上一个节点，将其与当前节点串起来，串起来后，prev更新为当前节点，由于第一个节点的设置，所以prev!=root才行
10         {
11              prev->right=root;
12              root->left=prev;
13              prev=root;
14         }
15         Convert(root->right);           　　　　　　　　　　　　　　 //转换右子树
16         return head;
17     }
18 };

其实就是按照中序遍历树节点，然后将上一个节点与当前节点串接起来。