我在代码随想录|写代码Day20之二叉树-700. 二叉搜索树中的搜索,98. 验证二叉搜索树,530.二叉搜索树的最小绝对差

学习目标：

博主介绍: 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;
    }
};