算法训练营20天|LeetCode 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

LeetCode 654.最大二叉树

题目链接：

LeetCode 654.最大二叉树

代码：

class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size()==1) return new TreeNode(nums[0]);
        int Index =0,max_num = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]>max_num){
                max_num = nums[i];
                Index=i;
            }
        }
        TreeNode*Node = new TreeNode(max_num);
        if(Index>0){
            vector<int>vec_left(nums.begin(),nums.begin()+Index);
            Node->left = constructMaximumBinaryTree(vec_left);
        }
        if(Index<nums.size()-1){
            vector<int>vec_right(nums.begin()+Index+1,nums.end());
            Node->right = constructMaximumBinaryTree(vec_right);
        }
        return Node;
    }
};

LeetCode 617.合并二叉树

题目链接：

LeetCode 617.合并二叉树

代码：

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr) return root2;
        if(root2 == nullptr) return root1;

        root1->val +=root2->val;
        
        root1->left = mergeTrees(root1->left,root2->left);
        root1->right = mergeTrees(root1->right,root2->right);
        return root1;
    }
};

LeetCode 700.二叉搜索树中的搜索

题目链接：

LeetCode 700.二叉搜索树中的搜索

代码：

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        queue<TreeNode*>que;
        if(root!=nullptr) que.push(root);
        while(!que.empty()){
            int size = que.size();
            for(int i=0;i<size;i++)
            {TreeNode*Node = que.front();
            que.pop();
            if(Node->val == val) return Node;
            if(Node->left) que.push(Node->left);
            if(Node->right) que.push(Node->right);}
        }
        return nullptr;
    }
};

LeetCode 98.验证二叉搜索树

题目链接：

LeetCode 98.验证二叉搜索树

解题思路：

将二叉树中序遍历，存为数组，看数组是否为递增的。

代码：

class Solution {
public:
    vector<int>vec;
    void traversal(TreeNode*root){
        if(root==nullptr) return;
        traversal(root->left);
        vec.push_back(root->val);
        traversal(root->right);
    }
    bool isValidBST(TreeNode* root) {
        traversal(root);
        for(int i =1;i<vec.size();i++){
            if(vec[i]<=vec[i-1]) return false;
        }
        return true;
    }
};