1.最大二叉树

654. 最大二叉树

这题与中序和后序构造二叉树有点相似

其实思路都是划分区域来构建二叉树，这里的构造是在区间范围内找到最大值

1.返回值为TreeNode*，参数为nums和规定取值范围的左右标志

2.如果left>right，说明此时递归结束，返回nullptr

3.首先建立节点才能在后续的左右节点建立关系，因此我们需要使用中序遍历。首先找出left到right范围内最大值和最大值的位置，此后构建节点，节点的left和right进行递归，传入的值分别是left,mid-1和mid+1,right。

class Solution {
public:TreeNode* _GetTreeR(vector<int>& nums,int left,int right){if(left>right)return nullptr;int mid = left;int max = nums[left];for(int i =left;i<=right;i++){if(nums[mid]<nums[i]){mid=i;max = nums[i];}}TreeNode* root = new TreeNode(max);root->left=_GetTreeR(nums,left,mid-1);root->right=_GetTreeR(nums,mid+1,right);return root;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {return _GetTreeR(nums,0,nums.size()-1);}
};

2.合并二叉树

617. 合并二叉树

此题其实就是构建二叉树，无非有一个注意的点是，root1和root2是否为空的问题

1.如果root1和root2都为空，那么说明本次递归结束，我们返回nullptr即可

2.依然采用的是前序遍历，中间节点的操作就是构造节点，首先构造节点指针，判断节点的情况：

如果两个节点都不为空，那么我们构造的节点值要二者相加，随后遍历root1和root2的左右节点

如果其中节点都为空，那么我们构造的节点值为另一个数，随后遍历空节点也要传入nullptr使得下一层的递归不越界访问

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

3.二叉搜索树的二分查找

700. 二叉搜索树中的搜索

其思想就是二分

1.如果root为nullptr，说明遍历结束

2.如果root的值与val相同，直接返回该root

3.如果不等，大于val要往左边递归找，小于val要往右边递归找

class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root==nullptr)return nullptr;if(root->val==val)return root;else if(root->val>val)return searchBST(root->left,val);elsereturn searchBST(root->right,val);return root;}
};

4.检验二叉搜索树

98. 验证二叉搜索树

检验二叉搜索树的方法就是左边是否小于根节点，右边是否大于根节点

需要注意的是，我们不能只看三个节点之间的比较，因为这样是不够的，打个比方：一个节点的右节点确实大于根节点，但是右节点的的左节点不仅小于右节点，还小于根节点，虽然它不是二叉搜索树，但是我们如果只是比较根左右的关系，那么一定是失败的。

class Solution {
public:bool isValidBST(TreeNode* root) {if(root==nullptr)return true;if(root->left){TreeNode* tmp = root->left;if(tmp->val>=root->val)return false;while(tmp->right){tmp = tmp->right;if(tmp->val>=root->val)return false;}}if(root->right){TreeNode* tmp = root->right;if(tmp->val<=root->val)return false;while(tmp->left){tmp = tmp->left;if(tmp->val<=root->val)return false;}}return isValidBST(root->left)&&isValidBST(root->right);}
};