青海住房与建设厅网站,热搜榜上2023年热搜,万网如何购买网站空间,wordpress ckeditor 中文字体今日总结#xff1a; 1、合并二叉树#xff1a; 在对两个二叉树进行递归操作的时候#xff0c;递归的停止条件不能是两棵树的节点都为空才停止#xff0c;因为在递归左右子节点的时候#xff0c;如果一个二叉树已经空了#xff0c;另一个没有空#xff0c;就会出现访问空…今日总结 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 (vectorintnums){//2、确定递归的停止逻辑//如果数组空了就返回nullptr表示叶子节点的下边的空节点if(nums.size()0)return nullptr;//3、确定单层递归的逻辑//1获取当前数组的最大值,及其位置int max0,where0;for(int i 0;inums.size();i){if(nums[i]max){max nums[i];where i;}}//2获取最大元素作为中间节点TreeNode* root new TreeNode(max);//3切割左右数组vectorintleft_num(nums.begin(),nums.begin()where);vectorintright_num(nums.begin()where1,nums.end());//去除中间节点//4递归左右子节点root-left digui(left_num);root-rightdigui(right_num);//5返回节点rootreturn root;}TreeNode* constructMaximumBinaryTree(vectorint 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(root1nullptr)return root2;if(root2nullptr)return root1;//3、确定递归的单层逻辑//这里我想使用前序遍历中、左、右不需要回溯只是操作一些点、没有上下的关联逻辑//1中记录当前的值.TreeNode* root new TreeNode();root-val root1-valroot2-val;//2左右递归root-left digui(root1-left,root2-left);root-right digui(root1-right,root2-right);//3返回当前节点rootreturn 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还没找到就返回nullptrif(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(rootnullptr)return true;//3、确定单层逻辑//使用中序遍历//递归左bool left_ digui(root-left);//记录中if(maxroot-val){//如果是就替换掉max的值max root-val;}如果不是就可以直接返回了else{return false;}//递归右bool right_ digui(root-right);//返回左右return left_ right_;}bool isValidBST(TreeNode* root) {return digui(root);}
}; 思路二二叉搜索树中序遍历会形成递增数组
