app设计网站模板,苏州市吴江太湖新城建设局网站,做网站三河,久久建筑网会员一、合并二叉树
1.题目
Leetcode#xff1a;第 617 题
给你两棵二叉树#xff1a; root1 和 root2 。
想象一下#xff0c;当你将其中一棵覆盖到另一棵之上时#xff0c;两棵树上的一些节点将会重叠#xff08;而另一些不会#xff09;。你需要将这两棵树合并成一棵新…一、合并二叉树
1.题目
Leetcode第 617 题
给你两棵二叉树 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]
2.解题思路
首先检查两个输入树的根节点是否为空如果其中一个为空则返回另一个作为结果。如果两个根节点都不为空将合并它们的值并对它们的左右子树递归地执行合并操作。这个过程一直持续到所有节点都被合并最终返回更新后的根节点包含了合并后二叉树的根。
3.实现代码
#include iostream
#include vector
#include queue
using namespace std;// 定义一个结构体TreeNode用于表示二叉树的节点。
struct TreeNode {int val; // 存储节点的值。TreeNode* left; // 指向该节点左子树的指针。TreeNode* right; // 指向该节点右子树的指针。// TreeNode的构造函数用于创建一个TreeNode实例。// 参数x是节点的值left和right默认为NULL表示没有左右子节点。TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 一、合并两棵二叉树递归法。
class Solution1 {
public:// mergeTrees函数用于合并两个给定的二叉树root1和root2。TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 NULL) return root2;// 如果root1为空则返回root2作为合并后的树的根节点。if (root2 NULL) return root1; // 如果root2为空则返回root1作为合并后的树的根节点。root1-val root1-val root2-val;// 将root1的值与root2的值相加并将结果赋给root1这是合并操作的一部分。root1-left mergeTrees(root1-left, root2-left);// 递归调用mergeTrees函数合并root1和root2的左子树。root1-right mergeTrees(root1-right, root2-right); // 递归调用mergeTrees函数合并root1和root2的右子树。return root1;// 返回更新后的root1作为合并后的树的根节点。}
};// 二、合并两棵二叉树迭代法法。
class Solution2 {
public:// mergeTrees函数用于合并两个给定的二叉树root1和root2。TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 NULL) return root2; // 如果root1为空直接返回root2作为合并后的树的根节点。if (root2 NULL) return root1; // 如果root2为空直接返回root1作为合并后的树的根节点。queueTreeNode* que; // 创建一个队列que用于在合并过程中存储待处理的节点对。que.push(root1); // 将root1和root2入队。que.push(root2);// 使用while循环处理队列中的所有节点对。while (!que.empty()) {// 取出队列中的两个节点node1对应root1的节点node2对应root2的节点。TreeNode* node1 que.front();que.pop();TreeNode* node2 que.front();que.pop();node1-val node1-val node2-val;// 将node1和node2的值相加并将结果赋给node1。// 如果node1和node2都有左子节点将它们入队以进行后续合并。if (node1-left ! NULL node2-left ! NULL) {que.push(node1-left);que.push(node2-left);}// 如果node1和node2都有右子节点将它们入队以进行后续合并。if (node1-right ! NULL node2-right ! NULL) {que.push(node1-right);que.push(node2-right);}//因为返回的是root1二叉树只需考虑考虑root1存在空节点对应的root2不为空节点的情况// 而不需要考虑root1存在节点对应的root2为空节点的情况// 如果node1没有左子节点但node2有左子节点将node2的左子节点赋给node1。if (node1-left NULL node2-left ! NULL) {node1-left node2-left;}// 如果node1没有右子节点但node2有右子节点将node2的右子节点赋给node1。if (node1-right NULL node2-right ! NULL) {node1-right node2-right;}//因为返回的是root1二叉树所以不需要考虑root1存在节点对应的root2为空节点的情况}return root1;// 由于函数只接收root1的指针返回root1此时它已经是合并后的树的根节点。}
};
二、二叉搜索树中的搜索
1.题目
Leetcode第 700 题
给定二叉搜索树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
输出[]
2.解题思路
首先检查当前根节点是否为空或者是否已经找到目标值。如果当前节点为空或者其值等于目标值则直接返回当前节点。如果当前节点的值大于目标值函数递归地在左子树中查找如果当前节点的值小于目标值则递归地在右子树中查找。最终函数返回查找结果如果找到了匹配的节点则返回该节点否则返回NULL。
3.实现代码
#include iostream
#include vector
#include queue
using namespace std;// 定义一个结构体TreeNode用于表示二叉树的节点。
struct TreeNode {int val; // 存储节点的值。TreeNode* left; // 指向该节点左子树的指针。TreeNode* right; // 指向该节点右子树的指针。// TreeNode的构造函数用于创建一个TreeNode实例。// 参数x是节点的值left和right默认为NULL表示没有左右子节点。TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 一、在二叉搜索树中查找特定值的节点递归法。
class Solution1 {
public:// searchBST函数用于在二叉搜索树root中查找值为val的节点。TreeNode* searchBST(TreeNode* root, int val) {if (root NULL || root-val val) return root; // 如果根节点为空或者根节点的值等于要查找的值val返回当前节点。TreeNode* result NULL;// 初始化结果指针为NULL用于存储找到的节点。if (root-val val) result searchBST(root-left, val);// 如果根节点的值大于要查找的值val递归搜索左子树。if (root-val val) result searchBST(root-right, val);// 如果根节点的值小于要查找的值val递归搜索右子树。 return result;// 返回搜索结果如果找到则返回找到的节点否则返回NULL。}
};// 二、在二叉搜索树中查找特定值的节点递归法。
class Solution2 {
public:// searchBST函数用于在二叉搜索树root中查找值为val的节点并返回。TreeNode* searchBST(TreeNode* root, int val) {while (root ! NULL) { // 使用while循环当root不为NULL时继续搜索。if (root-val val) {// 如果root的值大于要查找的值val向左子树搜索。root root-left;}else if (root-val val) {// 如果root的值小于要查找的值val向右子树搜索。root root-right;}else {// 如果root的值等于要查找的值val找到了目标节点返回root。return root;}}return NULL; //未找到就返回NULL。}
};三、验证二叉搜索树
1.题目
Leetcode第 98 题
给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下
节点的左 子树 只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 1 输入root [2,1,3]
输出true示例 2 输入root [5,1,4,null,null,3,6]
输出false
解释根节点的值是 5 但是右子节点的值是 4 。
2.解题思路
1.一般递归法递归遍历整个二叉树将所有节点的元素使用vector保存检查是否所有的元素都是严格递增的如果不是就说明不是一个有效的二叉搜索树。
2.双指针递归法在递归遍历整个二叉树的过程中用两个指针来检查是否满足每个节点的值都应该大于其左子树中所有节点的值并且小于其右子树中所有节点的值。如果不是就说明不是一个有效的二叉搜索树。
3.迭代法通过使用栈 st 来存储待访问的节点可以在每次循环中选择最左边的节点进行访问从而模拟中序遍历的过程。同时使用指针 pre 来记录遍历过程中的前一个节点值以便在访问当前节点时检查其是否违反了二叉搜索树的性质。如果遍历完整棵树都没有发现违反性质的情况则可以认为该二叉树是有效的二叉搜索树。
3.实现代码
#include iostream
#include vector
#include stack
using namespace std;// 定义一个结构体TreeNode用于表示二叉树的节点。
struct TreeNode {int val; // 存储节点的值。TreeNode* left; // 指向该节点左子树的指针。TreeNode* right; // 指向该节点右子树的指针。// TreeNode的构造函数用于创建一个TreeNode实例。// 参数x是节点的值left和right默认为NULL表示没有左右子节点。TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};// 一、验证二叉搜索树一般递归法。
class Solution {
public:vectorint vec; // 定义一个vec用于存储二叉树节点的值// 定义一个名为traversal的成员函数用于执行二叉树的中序遍历。void traversal(TreeNode* root) {if (root NULL) return; // 如果当前节点为空直接返回不执行任何操作。traversal(root-left); // 递归调用traversal函数遍历当前节点的左子树。vec.push_back(root-val); // 访问当前节点将其值添加到vec中。traversal(root-right); // 递归调用traversal函数遍历当前节点的右子树。}// 定义一个名为isValidBST的成员函数用于验证给定的二叉树是否为有效的二叉搜索树。// 参数root是二叉树的根节点指针。bool isValidBST(TreeNode* root) {vec.clear(); // 清空向量vec为新的中序遍历做准备。traversal(root); // 调用traversal函数传入根节点执行中序遍历。for (int i 1; i vec.size(); i) {// 遍历向量vec检查中序遍历的结果是否为升序。if (vec[i] vec[i - 1]) return false; // 如果发现任何违反升序的元素对返回false。}return true; // 如果遍历完成没有发现违反升序的元素对返回true表明是有效的二叉搜索树。}
};//二、验证二叉搜索树双指针递归法。
class Solution2 {
public:// 定义一个指向TreeNode的指针pre初始化为NULL用于在遍历过程中记录前一个访问的节点。TreeNode* pre NULL;// 定义一个名为isValidBST的成员函数用于验证给定的二叉树是否为有效的二叉搜索树。// 参数root是二叉树的根节点指针。bool isValidBST(TreeNode* root) {if (root NULL) return true; // 如果当前节点为空说明是有效的二叉搜索树返回true。// 递归调用isValidBST函数检查当前节点的左子树是否为有效的二叉搜索树。bool left isValidBST(root-left);// 如果pre不为NULL并且前一个访问的节点的值大于当前节点的值说明不是有效的二叉搜索树返回false。// 这是二叉搜索树的性质每个节点的值都应该大于其左子树中所有节点的值。if (pre ! NULL pre-val root-val) return false;pre root; // 更新pre为当前节点以便在递归检查右子树时使用。// 递归调用isValidBST函数检查当前节点的右子树是否为有效的二叉搜索树。bool right isValidBST(root-right);// 返回左子树和右子树的检查结果只有当左右子树都满足二叉搜索树的性质时整个树才是有效的。return left right;}
};// 三、验证二叉搜索树迭代法。
class Solution3 {
public:// 定义一个成员函数isValidBST用于验证给定的二叉树是否为有效的二叉搜索树。// 参数root是二叉树的根节点指针。bool isValidBST(TreeNode* root) {stackTreeNode* st; // 定义一个栈st用于存放二叉树的节点指针辅助进行迭代遍历。TreeNode* cur root; // 定义一个当前节点指针cur初始指向根节点。TreeNode* pre NULL; // 定义一个前一个节点指针pre初始为NULL用于记录遍历过程中的前一个节点值。// 当当前节点不为空或者栈st不为空时继续遍历。while (cur ! NULL || !st.empty()) {if (cur ! NULL) {// 如果当前节点不为空将当前节点压入栈st并将cur更新为当前节点的左子节点。st.push(cur); // 将当前节点压入栈中。cur cur-left; // 将cur更新为当前节点的左子节点开始遍历左子树。}else {// 如果当前节点为空从栈st中弹出一个节点作为当前节点。cur st.top(); // 获取栈顶节点。st.pop(); // 弹出栈顶节点。// 如果pre不为空并且当前节点的值小于pre记录的前一个节点的值说明不是有效的二叉搜索树返回false。// 这是二叉搜索树的性质每个节点的值都应该大于其左子树中所有节点的值。if (pre ! NULL cur-val pre-val) {return false;}pre cur;// 更新pre为当前节点。cur cur-right;// 将cur更新为当前节点的右子节点准备遍历右子树。}}// 如果遍历完整棵树都没有发现违反二叉搜索树性质的情况则返回true表明是有效的二叉搜索树。return true;}
};
ps以上皆是本人在探索算法旅途中的浅薄见解诚挚地希望得到各位的宝贵意见与悉心指导若有不足或谬误之处还请多多指教。
