代码随想录算法训练营第20天

标签：right TreeNode val 训练营 随想录 return 20 root left

今日刷题4道 654.最大二叉树， 617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树

●  654.最大二叉树

题目链接/文章讲解：https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1MG411G7ox

class Solution { public:     TreeNode* constructMaximumBinaryTree(vector<int>& nums) {         TreeNode* node = new TreeNode(0);         if(nums.size() == 1){             node -> val = nums[0];             return node;         }         int maxvalue = 0;         int maxvalueindex = 0;         for(int i=0;i<nums.size();i++){             if(nums[i] > maxvalue){                 maxvalue = nums[i];                 maxvalueindex = i;             }                   }         node->val = maxvalue;         if(maxvalueindex > 0){             vector<int> newvec(nums.begin(),nums.begin()+maxvalueindex);             node->left = constructMaximumBinaryTree(newvec);         }         if(maxvalueindex < (nums.size()-1)){             vector<int> newvec(nums.begin()+maxvalueindex+1,nums.end());             node->right = constructMaximumBinaryTree(newvec);         }         return node;     } };

●  617.合并二叉树

题目链接/文章讲解：https://programmercarl.com/0617.%E5%90%88%E5%B9%B6%E4%BA%8C%E5%8F%89%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV1m14y1Y7JK

 碎碎念：可以在原有的root1,root2上进行修改，也可以构造新的树。

class Solution { public:     TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {         if(root1==NULL) return root2;         if(root2==NULL) return root1;         TreeNode* root = new TreeNode(0);         root->val = root1->val+root2->val;         root->left=mergeTrees(root1->left,root2->left);         root->right=mergeTrees(root1->right,root2->right);         return root;     } };

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

题目链接/文章讲解: https://programmercarl.com/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.html

视频讲解：https://www.bilibili.com/video/BV1wG411g7sF

迭代法：

class Solution { public:     TreeNode* searchBST(TreeNode* root, int val) {         while(root !=NULL){             if(root->val < val) root=root->right;             else if(root->val > val) root = root->left;             else return root;         }         return NULL;     } }; 递归法： class Solution { public:     TreeNode* searchBST(TreeNode* root, int val) {        if(root==NULL || root->val==val) return root;        TreeNode* result = NULL;        if(root->val>val) result = searchBST(root->left, val);        if(root->val<val) result = searchBST(root->right,val);        return result;             } };

●  98.验证二叉搜索树

题目链接/文章讲解：https://programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

视频讲解：https://www.bilibili.com/video/BV18P411n7Q4

碎碎念：题目是真简单，用例是真过不去啊，不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。

中序遍历法：

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

递归法：

class Solution {
public:     long long maxval = LONG_MIN;     bool isValidBST(TreeNode* root) {        if(root == NULL) return true;        bool left = isValidBST(root->left);        if(maxval < root->val) maxval = root-> val;        else return false;        bool right = isValidBST(root->right);        return left&&right;

    } };

标签：right,TreeNode,val,训练营,随想录,return,20,root,left
From： https://www.cnblogs.com/zzw0612/p/17055596.html