1932. 合并多棵二叉搜索树-哈希法+深度优先遍历

给你 n 个 二叉搜索树的根节点 ，存储在数组 trees 中（下标从 0 开始），对应 n 棵不同的二叉搜索树。trees 中的每棵二叉搜索树 最多有 3 个节点 ，且不存在值相同的两个根节点。在一步操作中，将会完成下述步骤：

选择两个 不同的 下标 i 和 j ，要求满足在 trees[i] 中的某个 叶节点 的值等于 trees[j] 的 根节点的值 。
用 trees[j] 替换 trees[i] 中的那个叶节点。
从 trees 中移除 trees[j] 。
1
2
3

如果在执行 n - 1 次操作后，能形成一棵有效的二叉搜索树，则返回结果二叉树的 根节点 ；如果无法构造一棵有效的二叉搜索树，返回 null 。

二叉搜索树是一种二叉树，且树中每个节点均满足下述属性：

任意节点的左子树中的值都 严格小于 此节点的值。
任意节点的右子树中的值都 严格大于 此节点的值。
1
2

叶节点是不含子节点的节点。

示例 1：

输入：trees = [[2,1],[3,2,5],[5,4]]
输出：[3,2,5,1,null,4]
解释：
第一步操作中，选出 i=1 和 j=0 ，并将 trees[0] 合并到 trees[1] 中。
删除 trees[0] ，trees = [[3,2,5,1],[5,4]] 。

在第二步操作中，选出 i=0 和 j=1 ，将 trees[1] 合并到 trees[0] 中。
删除 trees[1] ，trees = [[3,2,5,1,null,4]] 。

结果树如上图所示，为一棵有效的二叉搜索树，所以返回该树的根节点。

示例 2：

输入：trees = [[5,3,8],[3,2,6]]
输出：[]
解释：
选出 i=0 和 j=1 ，然后将 trees[1] 合并到 trees[0] 中。
删除 trees[1] ，trees = [[5,3,8,2,6]] 。

结果树如上图所示。仅能执行一次有效的操作，但结果树不是一棵有效的二叉搜索树，所以返回 null 。

示例 3：

输入：trees = [[5,4],[3]]
输出：[]
解释：无法执行任何操作。

这题就很复杂，我们需要做很多操作，很离谱，感兴趣可以学习一下，解题代码如下所示：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
#define size 1777
int max,min;
struct hash{
    struct hash *next;
    struct TreeNode *node;
    int val;
    int index;
    int max;
    int min;

};
void add_hash(struct hash *h,struct TreeNode *node,int val,int index,int max,int min){
    struct hash *p=(struct hash *)malloc(sizeof(struct hash));
    p->node=node;
    p->val=val;
    p->next=h->next;
    p->max=max;
    p->min=min;
    p->index=index;
    h->next=p;
}

bool find(struct hash *h){
    struct hash *p=h->next;
    if(p){
        return true;
    }
    return false;
  
}
void delete(struct hash *h,struct TreeNode **leaf_node,int *r,int direction,int pre_val){
     struct hash *p=h->next;
     struct hash *pre=h;
     while(p){
        
         if(direction==1&&p->val==(*leaf_node)->val&&p->max<pre_val){
            pre->next=p->next;
             *leaf_node=p->node;
             r[p->index]=0;
         }
         else if(direction==0&&p->val==(*leaf_node)->val&&p->min>pre_val){
            pre->next=p->next;
            
             *leaf_node=p->node;
             r[p->index]=0;
         }
         pre=p;
         p=p->next;
     }

   

}
void post_order(struct TreeNode **root,struct hash *h,int *r,int direction,int pre_val){
    if((*root)){
      
        post_order(&((*root)->left),h,r,1,(*root)->val);
        
        post_order(&((*root)->right),h,r,0,(*root)->val);
        if((*root)->left==NULL&&(*root)->right==NULL){

            if(find(h+(*root)->val%size)){
                printf("leaf_val %d ",(*root)->val);

                delete(h+(*root)->val%size,root,r,direction,pre_val);
            }

        }

    }
    

}
void post_order2(struct TreeNode **root){
    if((*root)){
    
        post_order2(&((*root)->left));
        post_order2(&((*root)->right));   
        }
}

int inorder(struct TreeNode *root,int val){
    if(root){
        if(max<root->val){
            max=root->val;
        }
         if(min>root->val){
            min=root->val;
        }
         if(root->val>=val){
            return 1;
        }
        return inorder(root->left,val)||inorder(root->left,val);
        inorder(root->left,val);
        inorder(root->right,val);
    }
    else{
        return 0;
    }
}


int inorder2(struct TreeNode *root,int val){
    if(root){
        if(max<root->val){
            max=root->val;
        }
         if(min>root->val){
            min=root->val;
        }
         if(root->val<=val){
            return 1;
        }
        return inorder(root->left,val)||inorder(root->left,val);
        inorder(root->left,val);
        inorder(root->right,val);
    }
    else{
        return 0;
    }
}
int pre;
int pr;
void  judege(struct TreeNode *root){

    if(root&&pr){
        
        judege(root->left);
        if(pre>=root->val){
            pr=0;
        }
        else{
            pre=root->val;
        }
        judege(root->right);

    }
   
   
   


}

struct TreeNode* canMerge(struct TreeNode** trees, int treesSize){
    int *r=(int *)malloc(sizeof(int)*treesSize);
    struct hash *h=(struct hash *)malloc(sizeof(struct hash)*size);
    for(int i=0;i<size;i++){
        (h+i)->next=NULL;
    }
    for(int i=0;i<treesSize;i++){
        r[i]=1;
        max=trees[i]->val;
        min=trees[i]->val;
        if(inorder(trees[i]->left,trees[i]->val)==0&&inorder2(trees[i]->right,trees[i]->val)==0){
        //    printf("max min %d %d ",max,min);
             add_hash(h+(trees[i]->val)%size,trees[i],trees[i]->val,i,max,min);
        }
    }

      for(int i=0;i<treesSize;i++){

      post_order(&trees[i],h,r,-1,0);
        
    }
    int count=0;
    struct TreeNode *re;
    for(int i=0;i<treesSize;i++){
        if(r[i]!=0){
            post_order2(&trees[i]);
            count++;
            if(count>=2){
                return NULL;
            }

      //      printf("||%d ",trees[i]->val);
    
            re=trees[i];
        }
        
    }
    pre=-1;
  if(count==1){
      pr=1;
      judege(re);
      if(pr==0){
         
          return NULL;
      }
     
      return re;

  }
  return NULL;
    
    

    

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208