27 二叉搜索树与双向链表

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

C++:

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };*/
10 class Solution {
11 private:
12     TreeNode* pre = NULL ;
13     TreeNode* head = NULL ;
14 public:
15     TreeNode* Convert(TreeNode* pRootOfTree)
16     {
17         if (pRootOfTree == NULL)
18             return NULL ;
19         InOrder(pRootOfTree) ;
20         return head ;
21     }
22     
23     void InOrder(TreeNode* node){
24         if (node == NULL)
25             return ;
26         InOrder(node->left) ;
27         node->left = pre ;
28         if (pre != NULL){
29             pre->right = node ;
30         }
31         pre = node ;
32         if (head == NULL ){
33             head = node ;
34         }
35         InOrder(node->right) ;
36     }
37 };