day17 力扣654.最大二叉树 力扣617.合并二叉树 力扣700.二叉搜索树中的搜索 力扣98.验证二叉搜索树
最大二叉树
给定一个不重复的整数数组
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 <= 10000 <= nums[i] <= 1000nums中的所有整数 互不相同
本题与昨天最后一道题基本一样，同样是构造二叉树，我们需要找到区间内的最大值，作为索引，再分出俩个区间。
注意：
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 <= 107root是二叉搜索树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);}
};