99. 恢复二叉搜索树(深搜)

　　根据题意最直接的方法就是先中序遍历一遍二叉树，用vector记录下各个节点的值，对他们做排序，最后再中序遍历一遍按从小到大的顺序给节点赋值，算法时间复杂度：O(n)，空间复杂度：O(n)

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 bool cmp(int a, int b) {
11     return a > b;
12 }
13 class Solution {
14 public:
15     vector<int> list;
16     void recoverTree(TreeNode* root) {
17         if (!root) return;
18         dfs(root);
19         sort(list.begin(), list.end(), cmp); //给这课二叉树的各节点排序
20         modify(root);
21     }
22     void dfs(TreeNode* root) {
23         if (!root) return;
24         dfs(root->left);
25         list.push_back(root->val); //压入节点值
26         dfs(root->right);
27     }
28     void modify(TreeNode* root) {
29         if (!root) return;
30         modify(root->left);
31         root->val = list.back(); //按照中序遍历一次给节点赋值
32         list.pop_back(); 
33         modify(root->right);
34     }
35 };

时间复杂度为O(1)的暂时还没想到