最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值左边的 子数组前缀上 构建左子树。
递归地在最大值右边的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。
示例 1：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。- 空数组，无子节点。- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。- 空数组，无子节点。- 只有一个元素，所以子节点是一个值为 1 的节点。- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。- 只有一个元素，所以子节点是一个值为 0 的节点。- 空数组，无子节点。
示例 2：
输入：nums = [3,2,1]
输出：[3,null,2,null,1]
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums 中的所有整数 互不相同

本题与昨天最后一道题基本一样，同样是构造二叉树，我们需要找到区间内的最大值，作为索引，再分出俩个区间。

注意：

1.使用前序遍历，即中左右的形式。

2.我们可以在参数中加入左右索引，在后续构造左右的递归的时候，可以不需要再次构造新的vector数组，从而节约时间。

3.我们要考虑到每个区间内都至少包括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 {
public:TreeNode* traversal(vector<int>& nums,int leftIndex,int rightIndex){int index = 0;int maxNumber = INT_MIN;for(int i= leftIndex;i<rightIndex;i++){if(nums[i]>maxNumber){maxNumber = nums[i];index = i;}}TreeNode* newNode = new TreeNode(maxNumber);if(index>leftIndex){newNode->left = traversal(nums,leftIndex,index);}if(index<rightIndex-1){newNode->right = traversal(nums,index+1,rightIndex);}return newNode;}TreeNode* constructMaximumBinaryTree(vector<int>& nums) {if(nums.size()==1)return new TreeNode(nums[0]);return traversal(nums,0,nums.size());}
};

合并二叉树

给你两棵二叉树： root1 和 root2 。
想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1：
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]
示例 2：
输入：root1 = [1], root2 = [1,2]
输出：[2,2]
提示：
两棵树中的节点数目在范围 [0, 2000] 内
-104 <= Node.val <= 104

自己看这道题的时候，也想到了可以将root2这个二叉树加到root1中，但是没想到，如果root1的这个节点是null，但是root2相同节点非null，如何加进去。

其实我们只需要分别判断cur1，cur2是否为空，如果为空的话，直接return另一个节点就可以，这样的话相当于把另一部分的子二叉树全部移动到了root1。

这个题的代码还是很简洁的。

/*** 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 {
public:TreeNode* traversal(TreeNode* cur1, TreeNode* cur2){if(cur1==nullptr)return cur2;if(cur2==nullptr)return cur1;cur1->val+=cur2->val;cur1->left = traversal(cur1->left,cur2->left);cur1->right = traversal(cur1->right,cur2->right);return cur1;}TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {return traversal(root1,root2);}
};

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。
示例 1:
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]
示例 2:
输入：root = [4,2,7,1,3], val = 5
输出：[]
提示：
树中节点数在 [1, 5000] 范围内
1 <= Node.val <= 107
root 是二叉搜索树
1 <= val <= 107

二叉搜索树，判断条件：如果节点为空或值为目标值直接返回当前节点即可（为空返回null；为目标值返回当前节点）

如果当前值大于目标值，next往右节点走；反之往左节点走。

迭代法更是简单的没边，一个while循环解决。

/*** 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 {
public:TreeNode* traversal(TreeNode* cur, int value)//递归{if(cur==nullptr||cur->val==value)return cur;TreeNode* next = nullptr;if(value<cur->val) next = traversal(cur->left,value);if(value>cur->val) next  = traversal(cur->right,value);return next;}TreeNode* searchBST(TreeNode* root, int val) {return traversal(root,val);}
};

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效二叉搜索树定义如下：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1：
输入：root = [2,1,3]
输出：true
示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

这个题有一种解法，中序遍历，拿出所有的数放在vector容器中，判断这个容器是否为递增的，但这个效率不高。

还有就是我们不创造vector容器，直接在二叉树里判断。

我们定义一个treenode* pre，中序遍历，左右就是拿到递归子树的bool值，最后判断是否全部为真；中就是判断pre和root 的val的关系，注意pre要非空。

我们呢可以理解为这个解法也是隐式创建了一个递增数组（但我们实际并没有创建，也就是没有消耗时间空间）我们的pre和root相当于双指针，pre始终在root的左侧位置，且紧挨着root，不断判断二者关系，要始终让root>pre，一旦一次不是，那就是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 {
public:TreeNode* pre = nullptr; bool traversal(TreeNode* root){if(root==nullptr)return true;bool left = traversal(root->left);if(pre!=nullptr&&pre->val>=root->val)return false;pre = root;bool right = traversal(root->right);return left&&right;}bool isValidBST(TreeNode* root) {return traversal(root);}
};