Convert BST To Double Linked List

来源：EPI

原帖：EPI 11.9; EPI 6.9;

题目：
Design an algorith that takes as input a BST B and returns a sorted doubly linked list on the same elements. Your algorithm should not allocate any new nodes. The original BST does not have to be preserved; use its nodes as the nodes of the resulting list, as shown in Figure 11.4 on the previous page.

代码：

 // convert binary search tree to double linked list  
 struct TreeNode {  
   int val;  
   TreeNode* left;   
   TreeNode* right;  
   TreeNode(int v) : val(v), left(NULL), right(NULL) {}  
 };  
   
 void bst2dll(TreeNode* root, TreeNode* &head, TreeNode* &tail) {  
   if (!root) return;  
   bst2dll(root->left, head, tail);  
   if (!head) {  
     head = tail = root;  
   } else {  
     tail->right = root;  
     root->left = tail;  
     tail = root;  
   }  
   TreeNode* right = root->right;  
   root->right = NULL;  
   bst2dll(right, head, tail);  
 }  
   
 TreeNode* bst2dll(TreeNode* root) {  
   TreeNode *head = NULL, *tail = NULL;  
   bst2dll(root, head, tail);  
   return head;  
 }