1、题目描述

2/问题分析

利用中序遍历，然后重新构造树。

 

3、代码

 1 TreeNode* increasingBST(TreeNode* root) {
 2         if (root == NULL)
 3             return NULL;
 4         vector<int> v;
 5         inorder(root,v);
 6         
 7         TreeNode* dummy = new TreeNode(0);
 8         TreeNode *p = dummy;
 9         for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
10             TreeNode *tmp = new TreeNode(*it);
11             p->right = tmp;
12             p = p->right;
13         }
14         
15         return dummy->right;
16     }
17     
18     void inorder(TreeNode *root, vector<int> &v)
19     {
20         if (root == NULL)
21             return ;
22         inorder(root->left, v);
23         v.push_back(root->val);
24         inorder(root->right,v);
25     }