Leetcode算法训练日记 | day20

一、合并二叉树

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作为合并后的树的根节点。queue<TreeNode*> 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:vector<int> 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) {stack<TreeNode*> 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：以上皆是本人在探索算法旅途中的浅薄见解，诚挚地希望得到各位的宝贵意见与悉心指导，若有不足或谬误之处，还请多多指教。