//
// Created by 高森森 on 2022/2/18.
//

#ifndef LEETCODE_SOLUTION59_H
#define LEETCODE_SOLUTION59_H
#include<vector>
#include <iostream>
#include "Solution10.h"
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution59 {
public:
    unordered_map<int,TreeNode*>root;
    TreeNode* canMerge(vector<TreeNode*>& trees) {
        //首先如果叶子节点重复，不能构造二叉搜索树
        //而且必须只有一棵树的根节点不在叶子节点的集合中
        unordered_set<int>leaves;
        //检查叶子节点是否重复
        for(auto t:trees){
            //set的insert方法返回pair<迭代器，是否插入成功bool>
            //如果返回的bool值为false，说明叶子节点已经存在了，叶子节点重复
            //肯定没办法形成二叉搜索树，直接返回false
            if(t->left!=nullptr){
               if( leaves.insert(t->left->val).second== false)
                   return nullptr;
            }
            if(t->right!= nullptr){
                if( leaves.insert(t->right->val).second== false)
                    return nullptr;
            }
        }
        //检查是否只有一棵树的根节点不在叶子节点的集合中
        int count=0;
        TreeNode * binaryRoot;
        for(auto t:trees){
            if(leaves.count(t->val)){
                count++;
            }
            else{
                binaryRoot=t;
            }
        }
        if(count+1!=trees.size())
            return nullptr;
        //构造根节点的集合
        for(auto t:trees){
            if(t!=binaryRoot){
                root[t->val]=t;
            }
        }
        dfs(binaryRoot);
        if(!root.empty())
            return nullptr;
        vector<int>arr;
        midorder(binaryRoot,arr);
        if(isValid(arr))
            return binaryRoot;
        else
            return nullptr;

    }
   void dfs(TreeNode* node){
        if(node== nullptr){
            return ;
        }
        if(node->left== nullptr&&node->right==nullptr){
            auto it=root.find(node->val);
            if(it!=root.end()){
                node->left=root[node->val]->left;
                node->right=root[node->val]->right;
                root.erase(node->val);
            }
        }
        dfs(node->left);
        dfs(node->right);
    }
    void midorder(TreeNode *root,vector<int>&arr){
        if(root){
            midorder(root->left,arr);
            arr.push_back(root->val);
            midorder(root->right,arr);
        }
    }
    bool isValid(vector<int>arr){
        int n=arr.size();
        for(int i=0;i<n-1;i++){
            if(arr[i]>arr[i+1])
                return false;
        }
        return true;
    }
};


#endif //LEETCODE_SOLUTION59_H