今日总结：
1、合并二叉树：
在对两个二叉树进行递归操作的时候，递归的停止条件不能是两棵树的节点都为空才停止，因为在递归左右子节点的时候，如果一个二叉树已经空了，另一个没有空，就会出现访问空节点的错误。
而是在一个树空之后，直接返回另一棵树就行，因为后边的操作都是另一棵树自己的操作，空树不会再进行操作。
2、验证二叉搜索树：
二叉搜索树中序遍历会形成递增数组
前序递归+回溯与前序递归的场景总结
1、前序递归+回溯
前序遍历是指从根节点开始，依次访问左子树、右子树，遍历顺序是中->左->右，回溯是在递归中回退到上一层的节点进行处理。前序遍历+回溯用于：
（1）树的路径问题：例如查询从根节点到某叶子节点的路径、树中某个路径的和、找出所有路径和目标值匹配，回溯可以帮助在找到某个路径之后返回并继续遍历其他路径
（2）树状态的管理：例如查找某个条件的所有路径、遍历树的过程中需要进行某些状态管理，回溯用于在子树遍历完毕后恢复状态
2、前序遍历不需要回溯
在某些情况下，前序遍历足以解决问题，而不需要回溯。
（1）树的某些计算问题：当你只需要对树的每个节点执行某种操作（如求和、最大深度、查找最大最小值等），前序遍历即可，不需要回溯。因为每一层的计算是独立的，不需要退回到父节点继续计算。
3、总结：
前序遍历+回溯：处理树的多个路径或状态，在某条路径完成需要恢复路径
前序遍历：问题仅仅涉及树的某种全局计算，或树的搜索与处理是独立的，无需返回父节点恢复状态时。
最大二叉树
题目链接：654. 最大二叉树 - 力扣（LeetCode）
整体思路：
与通过后序数组、中序数组确定二叉树一样，这个可以通过前序递归的形式获取数组最大元素作为中间节点、切割左边数组为左子树、右边数组为右子树，整体比后序数组、中序数组确定二叉树简单
递归代码（与后序数组、中序数组确定二叉树类似）
/**
* 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:
//1、确定递归的传入参数、返回参数
//传入参数：数组、
//返回参数：二叉树
TreeNode* digui (vector<int>&nums)
{
//2、确定递归的停止逻辑
//如果数组空了就返回nullptr，表示叶子节点的下边的空节点
if(nums.size()==0)return nullptr;
//3、确定单层递归的逻辑
//（1）获取当前数组的最大值,及其位置
int max=0,where=0;
for(int i =0;i<nums.size();i++)
{
if(nums[i]>max)
{
max = nums[i];
where = i;
}
}
//（2）获取最大元素，作为中间节点
TreeNode* root = new TreeNode(max);
//（3）切割左右数组
vector<int>left_num(nums.begin(),nums.begin()+where);
vector<int>right_num(nums.begin()+where+1,nums.end());//去除中间节点
//（4）递归左右子节点
root->left = digui(left_num);
root->right=digui(right_num);
//（5）返回节点root
return root;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return digui (nums);
}
};合并二叉树
题目链接：617. 合并二叉树 - 力扣（LeetCode）
整体思路：
问题主要在于递归什么时候停止：与单个二叉树不同，合并二叉树是在一个二叉树为空，另一个不空就返回另一个，不需要往下遍历了
递归代码：
/**
* 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:
//使用递归进行合并
//1、确定递归的返回值、输入值
//返回值：新形成的节点
//输入值：两个节点
TreeNode* digui(TreeNode* root1, TreeNode* root2)
{
//2、确定递归的停止条件
//如果一棵树空了，返回另一棵树，不需要再往下遍历了
if(root1==nullptr)return root2;
if(root2==nullptr)return root1;
//3、确定递归的单层逻辑
//这里我想使用前序遍历中、左、右不需要回溯（只是操作一些点、没有上下的关联逻辑）
//（1）中：记录当前的值.
TreeNode* root = new TreeNode();
root->val = root1->val+root2->val;
//（2）左右：递归
root->left = digui(root1->left,root2->left);
root->right = digui(root1->right,root2->right);
//（3）返回当前节点root
return root;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return digui(root1,root2);
}
};二叉搜索树中的搜索
题目链接：700. 二叉搜索树中的搜索 - 力扣（LeetCode）
整体思路：
因为是搜索二叉树中的某个点，返回该节点，可以使用递归
1、确定递归的返回参数、输入参数、
返回参数：节点：存在就是节点，不存在就是nullptr
输入参数：当前节点，目标值
2、确定递归的停止条件：
当空节点就停止
3、确定单层递归的逻辑：
使用后序遍历：
先遍历左右节点，如果有匹配节点，就返回节点，
当前节点：如果左右节点有返回节点，就返回左右节点中的正确的值，如果没有就返回nullptr
递归代码：
/**
* 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:
//在搜索树中寻找一个值，返回值为根节点的子树，所以就是去遍历整棵二叉树，返回val所在的节点，可以使用递归
//1、确定递归的返回值、输入值
//返回值：返回的是一个节点，如果找到就返回该节点，如果没找到就返回nullptr
//输入值：输入的是当前节点，与目标值
TreeNode* digui(TreeNode* root ,int val)
{
//2、确定递归的停止条件
//如果找到了这个值，就停止遍历，开始返回
//如果递归到了nullptr还没找到，就返回nullptr
if(root ==nullptr)return nullptr;
//3、确定单层递归逻辑
//判断左子树、右子树
TreeNode* left_root = digui(root->left,val);
TreeNode* right_root = digui(root->right,val);
if(root->val == val)//如果找到了
{
return root;
}
if(left_root!=nullptr)return left_root;
else if(right_root!=nullptr)return right_root;
else return nullptr;
}
TreeNode* searchBST(TreeNode* root, int val) {
return digui(root,val);
}
};验证二叉搜索树
题目链接：98. 验证二叉搜索树 - 力扣（LeetCode）
整体思路：
思路一：
因为是验证二叉搜索树，需要判断左子节点总是比当前节点小，右子节点总是比当前节点大
可以使用中序遍历
1、递归左子树
2、记录当前值：使用一个全局变量，与当前节点比大小，如果小于当前节点，此时就是正常的二叉搜索树，将当前节点的值赋值给全局变量；如果全局变量大于当前节点，就直接返回false，说明这不是二叉搜索树，
3、递归右子树
4、最终返回左子树&&右子树
/**
* 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:
//定义一个全局最小值，从下往上从左往右开始判断
long long max = LONG_MIN;
//左子树比中间节点小
//右子树比中间节点大
//递归
//1、确定递归的返回值、输入值
//返回值：bool类型的是不是满足左子树<中间节点，右子树>中间节点
//输入值：当前节点
bool digui(TreeNode* root)
{
//2、确定递归的停止
//当遇到nullptr就停止
if(root==nullptr)return true;
//3、确定单层逻辑
//使用中序遍历
//递归左
bool left_ = digui(root->left);
//记录中
if(max<root->val)
{
//如果是，就替换掉max的值
max = root->val;
}
如果不是，就可以直接返回了
else
{
return false;
}
//递归右
bool right_ = digui(root->right);
//返回左右
return left_&& right_;
}
bool isValidBST(TreeNode* root) {
return digui(root);
}
};思路二：二叉搜索树中序遍历会形成递增数组
转载自CSDN-专业IT技术社区
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/m0_47408374/article/details/148626015
