又是破防的一天......
一.654最大二叉树
又是构造二叉树，昨天大家刚刚做完 中序后序确定二叉树，今天做这个 应该会容易一些， 先看视频，好好体会一下 为什么构造二叉树都是 前序遍历
题目链接：最大二叉树
文章讲解：代码随想录
1.思路分析
简单来说，二叉树构建过程如下：
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
递归三部曲：
1）确定递归函数的参数和返回值
参数传入的是存放元素的数组以及左右边界索引，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。
struct TreeNode* traversal(int* nums, int left, int right)2）确定终止条件
当左右边界相等或左右颠倒时，返回NULL。
//若左边界大于右边界，返回NULL
if(left >= right)
return NULL;3）确定单层递归的逻辑
第一步：先要找到数组中最大的值和对应的下标， 最大的值构造根节点，下标用来下一步分割数组。
//找出数组中最大数坐标
int maxIndex = left;
int i;
for(i = left + 1; i < right; i++) {
if(nums[i] > nums[maxIndex])
maxIndex = i;
}
//开辟结点
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
//将结点的值设为最大数组数组元素
node->val = nums[maxIndex];第二步：最大值所在的下标左区间构造左子树。
node->left = traversal(nums, left, maxIndex);第三步：最大值所在的下标右区间构造右子树。
node->right = traversal(nums, maxIndex + 1, right);2.代码详解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* traversal(int* nums, int left, int right) {
//若左边界大于右边界，返回NULL
if(left >= right)
return NULL;
//找出数组中最大数坐标
int maxIndex = left;
int i;
for(i = left + 1; i < right; i++) {
if(nums[i] > nums[maxIndex])
maxIndex = i;
}
//开辟结点
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
//将结点的值设为最大数组数组元素
node->val = nums[maxIndex];
//递归定义左孩子结点和右孩子结点
node->left = traversal(nums, left, maxIndex);
node->right = traversal(nums, maxIndex + 1, right);
return node;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize){
return traversal(nums, 0, numsSize);
}二.617合并二叉树
这次是一起操作两个二叉树了， 估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。 优先掌握递归。
题目链接：合并二叉树
文章讲解：代码随想录
1.思路分析
其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。
这道题用哪种遍历都可以，本人以前序为例。
递归三部曲：
1）确定递归函数的参数和返回值
首先要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2)2）确定终止条件
因为是传入了两个树，那么就有两个树遍历的节点root1 和 root2，如果root1 == NULL 了，两个树合并就应该是 root2 了（如果root2也为NULL也无所谓，合并之后就是NULL）。
反过来如果root2 == NULL，那么两个数合并就是root1（如果root1也为NULL也无所谓，合并之后就是NULL）。
代码如下：
if (root1 == NULL) return root2; // 如果root1为空，合并之后就应该是root2
if (root2 == NULL) return root1; // 如果root2为空，合并之后就应该是root13）确定单层递归的逻辑
单层递归的逻辑就比较好写了，这里我们重复利用一下root1这个树，root1就是合并之后树的根节点（就是修改了原来树的结构）。
那么单层递归中，就要把两棵树的元素加到一起。
root->val=root1->val+root2->val;接下来root1 的左子树是：合并root1左子树root2左子树之后的左子树。
root1 的右子树：是 合并 root1右子树 root2右子树之后的右子树。
最终t1就是合并之后的根节点。
root->left=mergeTrees(root1->left,root2->left);
root->right=mergeTrees(root1->right,root2->right);
return root;2.代码详解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
if(root1==NULL) return root2;
if(root2==NULL) return root1;
struct TreeNode* root=(struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val=root1->val+root2->val;
root->left=mergeTrees(root1->left,root2->left);
root->right=mergeTrees(root1->right,root2->right);
return root;
}三.700二叉搜索树中的搜索
递归和迭代 都可以掌握以下，因为本题比较简单， 了解一下 二叉搜索树的特性
1.思路分析
本题，其实就是在二叉搜索树中搜索一个节点。那么我们来看看应该如何遍历。
递归三部曲：
1）确定递归函数的参数和返回值
递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。
代码如下：
struct TreeNode* searchBST(struct TreeNode* root, int val)2）确定终止条件
如果root为空，或者找到这个数值了，就返回root节点。
if (root == NULL || root->val == val) return root;3） 确定单层递归的逻辑
看看二叉搜索树的单层递归逻辑有何不同。
因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。
如果root->val 大于val，搜索左子树，如果root->val 小于 val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
struct TreeNode* result = NULL;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;很多人写递归函数的时候习惯直接写searchBST(root->right, val)，却忘了递归函数还有返回值。
递归函数的返回值是什么? 是左子树如果搜索到了val，要将该节点返回。 如果不用一个变量将其接住，那么返回值不就没了。
所以要result = searchBST(root->right, val);并在最后return result。
2.代码详解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* searchBST(struct TreeNode* root, int val) {
if (root == NULL || root->val == val) return root;
struct TreeNode* result = NULL;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;
}四.98验证二叉搜索树
遇到 搜索树，一定想着中序遍历，这样才能利用上特性。
1.思路分析
要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
这道题目比较容易陷入两个陷阱：
- 陷阱1
不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
我们要比较的是 左子树所有节点小于中间节点，右子树所有节点大于中间节点。
例如： [10,5,15,null,null,6,20] 这个case：
节点10大于左节点5，小于右节点15，但右子树里出现了一个6 这就不符合了！
- 陷阱2
样例中最小节点可能是int的最小值，如果这样使用最小的int来比较也是不行的。
此时可以初始化比较元素为longlong的最小值。
（不过本人写的代码并没有考虑longlong的情况，所以如果你比较顾虑，可以自行修改）
递归三部曲：
1）确定递归函数的参数和返回值
bool isValid(struct TreeNode* root,struct TreeNode** pre)（悄悄话：其中，pre为用来记录前一个节点的指针的指针，我一开始本想当作全局变量放在函数前面。测试的时候没问题，但是提交的时候，面对{0}的输入，输出错误，也不知道怎么回事。如果你平时有认真看我的博客的话，你会发现我上一次也用了指针的指针来代替全局变量，错误的具体原因我也不太清楚，这也是我今天破防的原因。我回头再研究一下。我破防的另一个原因是，在第三题，我遍历的时候脑袋短路了，当时就是不明白为什么在最后要写返回值......）
2）确定终止条件
如果是空节点 是不是二叉搜索树呢？
是的，二叉搜索树也可以为空！
if (root == NULL) return true;3）确定单层递归的逻辑
bool left = isValid(root->left,pre);
if (*pre != NULL && (*pre)->val >= root->val) return false;
*pre = root; // 记录前一个节点
bool right = isValid(root->right,pre);
return left && right;2.代码详解
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isValid(struct TreeNode* root,struct TreeNode** pre) {
if (root == NULL) return true;
bool left = isValid(root->left,pre);
if (*pre != NULL && (*pre)->val >= root->val) return false;
*pre = root; // 记录前一个节点
bool right = isValid(root->right,pre);
return left && right;
}
bool isValidBST(struct TreeNode* root){
struct TreeNode* pre = NULL;
return isValid(root,&pre);
}如果你有问题或者有其他想法，欢迎评论区留言，大家可以一起探讨。