题目链接：https://leetcode.cn/problems/maximum-binary-tree/description/
思路：
? ? ? ? 本题目要求我们根据已知数组构建一颗最大二叉树，最大值为根节点，最大值左边区间构建左子树，最大值右边区间构建右子树。
? ? ? ? 很容易我们就能想到这道题目要用递归来实现，因为针对每个区间我们的操作都是相同的：先寻找最大值构建根节点，再分割左右区间构建左右子树。因此我们对总区间 [0,n-1] 进行递归处理，递归边界条件为 l==r-1 ，即区间中只有一个点，这时就到达了叶子节点，不用再向下构建了，挨层回溯子树根节点即可，最后总区间回溯出的节点就是整颗树的根节点。
核心代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
TreeNode* createTree(vector<int>& nums,int l,int r){
if(l>=r||l<0||r>nums.size()) return NULL;
int maxval=l;
for(int i=l;i<r;i++)
if(nums[i]>nums[maxval]) maxval=i;
TreeNode* cur=new TreeNode(nums[maxval]);
cur->left=createTree(nums,l,maxval);
cur->right=createTree(nums,maxval+1,r);
return cur;
}
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return createTree(nums,0,nums.size());
}
};题目链接：https://leetcode.cn/problems/merge-two-binary-trees/description/
思路：
? ? ? ? 本题要求我们将两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为?null 的节点将直接作为新二叉树的节点。
? ? ? ? 我们从根节点开始，考虑每个节点的情况，分别处理即可，分析以后会发现很简单。
? ? ? ? 我们先假设两棵树为树1和树2，当前处理到的位置相同的点为cur1和cur2，其中cur1为树1的节点，cur2为树2的节点。下面我们分类讨论：
? ? ? ? 1.如果cur1和cur2都是空节点，那么新树中这个点必定为空，就不用向下处理了，向下肯定也是空的，因为下面已经没有点了。
? ? ? ? 2.如果cur1是空节点，cur2不是空节点，那么新树中以当前位置这个点为根节点的子树，其构造必定和树2中以cur2为根节点的子树完全一致，因为cur1是空的，那么树1以cur1为根节点的子树也必定为空，那就不会向cur2那颗子树合并，或者说合并后还是cur2那颗子树，所以我们返回cur2即可，也不必再向下构造了。
? ? ? ? 3.如果cur1不是空节点，cur2是空节点，那么这种情况与2重复，同样的处理方式即可，不过这次返回的是cur1这棵子树，或者说树1的cur1节点。
? ? ? ? 4.如果cur1和cur2都不是空节点，那么我们将其值合并，变成新节点赋给新树对应位置节点，然后分别递归处理左右儿子，左右儿子的情况又回到这四种情况中，判断是哪种情况处理即可。
核心代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
TreeNode* merge(TreeNode* cur1,TreeNode* cur2){
if(!cur1&&!cur2) return NULL;
if(!cur1) return cur2;
if(!cur2) return cur1;
cur1->val+=cur2->val;
cur1->left=merge(cur1->left,cur2->left);
cur1->right=merge(cur1->right,cur2->right);
return cur1;
}
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return merge(root1,root2);
}
};题目链接：https://leetcode.cn/problems/search-in-a-binary-search-tree/description/
思路：
? ? ? ?本题要求我们在 BST 中找到节点值等于?val?的节点。 返回以该节点为根的子树。 如果节点不存在，则返回?null?。
? ? ? ? 思路也很简单，递归向下搜索即可。每次判断当前节点的值与val的大小关系，如果val大，就向右子树去搜，如果val小，就向左子树去搜，搜到空节点或者值相等为止。值相等证明找到了，返回当前节点，空节点证明树中没有该值，返回空即可。
核心代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
TreeNode* searchval(TreeNode* cur,int val){
if(!cur) return NULL;
else if(cur->val==val) return cur;
else if(cur->val>val) return searchval(cur->left,val);
else return searchval(cur->right,val);
}
public:
TreeNode* searchBST(TreeNode* root, int val) {
return searchval(root,val);
}
};题目链接：https://leetcode.cn/problems/validate-binary-search-tree/description/
思路：
? ? ? ? 本题目要求我们判断一棵树是否是一个有效的二叉搜索树。
? ? ? ? 首先我们要知道，所谓的有效的二叉搜索树，就是说针对树中任意非空节点作为根节点来说，左子树的最大值小于根节点值，右子树的最小值大于根节点值。因此我们从根节点开始递归的处理每棵子树即可。
? ? ? ? 我们可以开一个全局变量flag，记录整颗树是否合法。也就是递归的时候处理到不合法情况让flag值为false即可。递归结束后flag为true证明整颗树合法，反之则不合法。flag初始值为true。
????????每层递归我们要做的事情如下：递归处理左子树的最大值和最小值，递归处理右子树的最大值和最小值。得到这四个值结合根节点值我们就可以判断整颗树是否合法，从而决定flag是否为false。同时我们可以得到整颗树的最小值和最大值，向上一层回溯这两个值即可。
????????注意递归的边界条件为左右儿子均为空节点，即当前子树只有一个节点，就是总树的叶子节点，这时子树的最大值和最小值相同，均为子树根节点值。
核心代码：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
private:
bool flag=true;
vector<int> isValid(TreeNode* cur){
vector<int> nums;
int minnum=cur->val,maxnum=cur->val;
if(cur->left){
vector<int> numl=isValid(cur->left);
if(numl[0]<minnum) minnum=numl[0];
if(numl[1]>maxnum) maxnum=numl[1];
if(numl[1]>=cur->val){
flag=false;
}
}
if(cur->right){
vector<int> numr=isValid(cur->right);
if(numr[0]<minnum) minnum=numr[0];
if(numr[1]>maxnum) maxnum=numr[1];
if(numr[0]<=cur->val){
flag=false;
}
}
nums.push_back(minnum);
nums.push_back(maxnum);
return nums;
}
public:
bool isValidBST(TreeNode* root) {
isValid(root);
return flag;
}
};????????今日学习时长2h，题目不算难，但我的解法不算好，肯定有更好的解法，还没来得及看，因为这两天又要准备期末，先把期末过了再说。