leetcode1932 合并多棵二叉搜索树

思路：

模拟，细节比较多。参考了https://leetcode-cn.com/problems/merge-bsts-to-create-single-bst/solution/fen-xiang-xia-si-kao-guo-cheng-by-time-l-6o84/

实现：

 1 class Solution
 2 {
 3 public:
 4     void dfs(TreeNode* root, vector<int>& v)
 5     {
 6         if (root == NULL) return;
 7         dfs(root->left, v);
 8         v.push_back(root->val);
 9         dfs(root->right, v);
10     }
11     TreeNode* canMerge(vector<TreeNode*>& trees)
12     {
13         map<int, TreeNode*> mp;
14         map<TreeNode*, TreeNode*> par;
15         int cnt = 0;
16         for (auto it: trees)
17         {
18             if (it->left)
19             {
20                 int tmp = it->left->val;
21                 if (mp.count(tmp)) return NULL;
22                 mp[it->left->val] = it->left;
23                 par[it->left] = it;
24                 cnt++;
25             }
26             if (it->right)
27             {
28                 int tmp = it->right->val;
29                 if (mp.count(tmp)) return NULL;
30                 mp[it->right->val] = it->right;
31                 par[it->right] = it;
32                 cnt++;
33             }
34         }
35         TreeNode* root = NULL;
36         for (auto it: trees)
37         {
38             int tmp = it->val;
39             if (!mp.count(tmp))
40             {
41                 if (root) return NULL;
42                 else root = it;
43             }
44             else
45             {
46                 TreeNode* x = mp[tmp];
47                 TreeNode* p = par[x];
48                 if (x == p->left) p->left = it;
49                 else p->right = it;
50                 delete(x);
51             }
52         }
53         vector<int> res;
54         dfs(root, res); 
55         int n = res.size();
56         if (n != cnt + 1) return NULL;
57         bool flg = true;
58         for (int i = 0; i < n - 1; i++)
59         {
60             if (res[i] >= res[i + 1]) { flg = false; break; }
61         }
62         if (!flg) return NULL;
63         return root;
64     }
65 };