学习目标：
博主介绍: 27dCnc
专题 : 数据结构帮助小白快速入门
👍👍👍👍👍👍👍👍👍👍👍👍
☆*: .｡. o(≧▽≦)o .｡.:*☆
主题: 二叉树
今日份打卡
- 代码随想录-二叉树
学习内容：
- 二叉搜索树中的搜索
- 验证二叉搜索树
- 二叉搜索树的最小绝对差
内容详细 :
700. 二叉搜索树中的搜索
题目考点 : 二叉搜索树 递归
递归法
- 确定递归函数的参数和返回值
递归函数的参数传入的就是根节点和要搜索的数值，返回的就是以这个搜索数值所在的节点。
TreeNode* searchBST(TreeNode* root, int val)
- 确定终止条件
如果root为空，或者找到这个数值了，就返回root节点。
if (root == NULL || root->val == val) return root;
- 确定单层递归的逻辑
因为二叉搜索树的节点是有序的，所以可以有方向的去搜索。 如果root->val > val，搜索左子树，如果root->val < val，就搜索右子树，最后如果都没有搜索到，就返回NULL。
TreeNode* result = NULL;
if (root->val > val) result = searchBST(root->left, val);
if (root->val < val) result = searchBST(root->right, val);
return result;
整体代码
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == NULL || root->val == val) return root;
if (root->val > val) return searchBST(root->left, val);
if (root->val < val) return searchBST(root->right, val);
return NULL;
}
};
迭代法
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
while(root != nullptr) {
if(val == root->val) return root;
else if(val < root->val) root = root->left;
else if(val > root->val) root = root->right;
}
return nullptr;
}
};
98. 验证二叉搜索树
题目 : 二叉搜索树 深度优先搜索(即遍历二叉树)
思路
要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了
验证最好的方法就是找反例二叉搜索树中不能有重复元素。
特殊情况确定
迭代法
class Solution {
public:
vector<int>vec;
void traversal(TreeNode* root) {
if(root == nullptr) return;
traversal(root->left);
vec.push_back(root->val);
traversal(root->right);
}
bool isValidBST(TreeNode* root) {
vec.clear();//让数组保持为空
traversal(root);
for(int i = 1;i<vec.size();i++) {
if(vec[i] <= vec[i-1]) return 0;
}
return 1;
}
};
递归法
class Solution {
public:
TreeNode* pre = NULL; // 用来记录前一个节点
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
bool left = isValidBST(root->left);
if (pre != NULL && pre->val >= root->val) return false;
pre = root; // 记录前一个节点
bool right = isValidBST(root->right);
return left && right;
}
};
530.二叉搜索树的最小绝对差
题目考点 : 二叉搜索树 二叉搜索树的性质
图解
思路 : 二叉搜索树采用中序遍历，其实就是一个有序数组。
在一个有序数组上求两个数最小差值
递归法
class Solution {
private:
int result = INT_MAX;
TreeNode* pre = NULL;
void traversal(TreeNode* cur) {
if (cur == NULL) return;
traversal(cur->left); // 左
if (pre != NULL){
// 中
result = min(result, cur->val - pre->val);
}
pre = cur; // 记录前一个
traversal(cur->right); // 右
}
public:
int getMinimumDifference(TreeNode* root) {
traversal(root);
return result;
}
};
迭代法
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
TreeNode* pre = NULL;
int result = INT_MAX;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
// 指针来访问节点，访问到最底层
st.push(cur); // 将访问的节点放进栈
cur = cur->left; // 左
} else {
cur = st.top();
st.pop();
if (pre != NULL) {
// 中
result = min(result, cur->val - pre->val);
}
pre = cur;
cur = cur->right; // 右
}
}
return result;
}
};
学习时间：
- 周一至周五晚上 7 点—晚上9点
- 周六上午 9 点-上午 11 点
- 周日下午 3 点-下午 6 点
学习产出：
- 技术笔记 2 遍
- CSDN 技术博客 3 篇
- 习的 vlog 视频 1 个
🔥如果此文对你有帮助的话，欢迎💗关注、👍点赞、⭐收藏、✍️评论，支持一下博主~
