class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode*root=new TreeNode(0);
        if(nums.size()==1)
        {
            root->val=nums[0];        //数组只有一个数的时候，可以直接返回
            return root;
        }
        int max=-100,maxindex=0;    
        for(int i=0;i<nums.size();i++)        //遍历数组
        {
            if(nums[i]>max)                //找出最大值及其下标
            {
                max=nums[i];
                maxindex=i;
            }
        }
        root->val=max;        //建好中节点数值
        if(maxindex>0)        //判断左子树是否有元素
        {
            vector<int> lefttree(nums.begin(),nums.begin()+maxindex);
            root->left=constructMaximumBinaryTree(lefttree);
        }
        if(maxindex<nums.size()-1)          //判断右子树是否有元素
        {
            vector<int> righttree(nums.begin()+maxindex+1,nums.end());
            root->right=constructMaximumBinaryTree(righttree);
        }
        return root;
    }
};

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==NULL)            //一个有空就返回另外一个
        {
            return root2;
        }
        if(root2==NULL)
        {
            return root1;
        }
        TreeNode*node=new TreeNode(0);        //建立节点
        node->val=root1->val+root2->val;        //都有就加起来
        node->left=mergeTrees(root1->left,root2->left);    //遍历
        node->right=mergeTrees(root1->right,root2->right);
        return node;
    }
};

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(root==NULL)             
        {
            return NULL;
        }
        if(root->val==val)        //找到了就返回
        {
            return root;
        }
        if(root->left==NULL&&root->right==NULL)        //叶子节点也返回
        {
            return NULL;
        }
        TreeNode*node=NULL;            //创建节点存值
        if(val>root->val)            //根据搜索树的定义，分两边搜索
        {
            node=searchBST(root->right,val);
        }
        if(val<root->val)
        {
            node=searchBST(root->left,val);
        }
        return node;
    }
};

class Solution {
public:
    long long maxval=LONG_MIN;        //设定最小值
    bool isValidBST(TreeNode* root) {
        if(root==0)
        {
            return true;                    //空节点就返回
        }
        bool left=isValidBST(root->left);        //左遍历
        if(maxval<root->val)            //一层一层赋值，递增
        {
            maxval=root->val;
        }
        else                //有违法的直接false，就再也没有机会翻身了。
        {
            return false;
        }
        bool right=isValidBST(root->right);    
        return right&&left;
    }
};