程序员面试100题--01

 1 #include <iostream>
 2 #include <string>
 3 #include <memory.h>
 4 #include <vector>
 5 #include <sstream>
 6 #include <math.h>
 7 using namespace std;
 8 
 9 /*
10 思路：
11 递归的转化左子树以及右子树，然后将当前节点作为左子树链表的末尾节点，
12 作为右子树的链表的开头结点.
13 但是得记住需要左子树的最后一个节点以及右子树的第一个节点
14 */
15 struct TreeNode
16 {
17     int val;
18     TreeNode *left;
19     TreeNode *right;
20     TreeNode(int x):val(x),left(NULL),right(NULL)
21     {
22 
23     }
24 };
25 TreeNode* ConvertNode(TreeNode *pNode,bool isRight)
26 {
27     if(pNode == NULL)
28         return NULL;
29     TreeNode* left = pNode->left;
30     TreeNode* right = pNode->right;
31     TreeNode* preturn = NULL;
32     TreeNode* root = pNode;
33     if(isRight)
34     {
35         while(root->left)
36             root = root->left;
37         preturn = root;
38     }
39     else
40     {
41         while(root->right)
42             root = root->right;
43         preturn = root;
44     }
45 
46     TreeNode* pLeft = NULL;
47     if(left != NULL)
48     {
49         pLeft = ConvertNode(left);
50     }
51     if(pLeft != NULL)
52         pLeft->right = pNode;
53     pNode->left = pLeft;
54 
55     TreeNode* pRight = NULL;
56     if(right != NULL)
57     {
58         pRight = ConvertNode(right);
59     }
60     if(pRight != NULL)
61         pRight->left = pNode;
62     pNode->right = pRight;
63     return preturn;
64 }
65 
66 int main()
67 {
68 
69     return 0;
70 }
题目描述：把二叉排序树转换成排序双向链表