Skip to content

Latest commit

 

History

History
359 lines (340 loc) · 12.7 KB

二叉搜索树.md

File metadata and controls

359 lines (340 loc) · 12.7 KB
Raw

二叉搜索树

leetcode.700 二叉搜索树中的搜索

  • 链接https://leetcode.cn/problems/search-in-a-binary-search-tree/
  • 解题思路：
    递归函数功能：在二叉搜索树中找以 val 为根的子树
    1. 递归终止条件：
      如果根节点不存在则返回空节点
      如果根节点的值等于 val 则返回根节点
    2. 递归逻辑：
      如果根节点的值大于 val 则说明 val 在左子树，在左子树中找
      如果根节点的值小于 val 则说明 val 在右子树，在右子树中找
    3. 递归返回值：返回新的根节点
  • 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:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (!root) return nullptr;
        if (root->val == val) return root;

        TreeNode* new_root = nullptr;
        if (root->val > val) new_root = searchBST(root->left, val);
        if (root->val < val) new_root = searchBST(root->right, val);
        return new_root;
    }
};

leetcode.98 验证二叉搜索树

  • 链接https://leetcode.cn/problems/validate-binary-search-tree/
  • 解题思路：
    递归函数功能：判断二叉搜索树中序遍历是否有序
    1. 递归终止条件：
      如果根节点不存在则有序
    2. 递归逻辑：
      中序遍历中如果上一个节点存在并且 >= 根节点说明无序
      更新节点
    3. 递归返回值：返回二叉搜索树中序遍历有序的条件
      左子树有序并且右子树有序
  • 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:
    // 记录上一个节点
    TreeNode* pre;
    bool isValidBST(TreeNode* root) {
        return dfs(root);
    }
    // 判断中序遍历是否有序
    bool dfs(TreeNode* root){
        if (!root) return true;
        
        auto l = dfs(root->left);

        if (pre && pre->val >= root->val) return false;
        pre = root;

        auto r = dfs(root->right);
        return l && r;
    }
};

leetcode.530 二叉搜索树的最小绝对差

  • 链接https://leetcode.cn/problems/minimum-absolute-difference-in-bst/
  • 解题思路：
    递归函数功能：计算二叉搜索树中序遍历相邻两个数的最小绝对差
    1. 递归终止条件：
      如果根节点不存在则结束递归
    2. 递归逻辑：
      中序遍历中如果上一个节点存在则计算差值，并更新答案
      更新节点
  • 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:
    int res = INT_MAX;
    // 记录上一个节点
    TreeNode* pre;
    int getMinimumDifference(TreeNode* root) {
        dfs(root);
        return res;
    }
    // 中序遍历，最小绝对差一定是相邻的两个数
    void dfs(TreeNode* root){
        if (!root) return;

        dfs(root->left);

        if (pre) res = min(res, root->val - pre->val);
        pre = root;

        dfs(root->right);
    }
};

leetcode.501 二叉搜索树中的众数

  • 链接https://leetcode.cn/problems/find-mode-in-binary-search-tree/
  • 解题思路：
    递归函数功能：计算二叉搜索树中序遍历最长连续的一段序列
    1. 递归终止条件：
      如果根节点不存在则结束递归
    2. 递归逻辑：
      如果当前值和上一个值相等，当前计数 +1
      如果不相等，说明是一个新的序列，当前计数 =1
      更新当前数
      如果当前计数 > 最大计数，更新最大计数并更新答案
      如果当前计数和最大计数相等，说明不止众数不止一个，加入答案
  • 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:
    vector<int> res;
    // 记录当前序列中数的个数，记录最大的序列中数的个数，记录上一个数
    int curc = 0, maxc = 0, pre;
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return res;
    }
    // 中序遍历，相同的数会是一段连续的序列
    void dfs(TreeNode* root){
        if (!root) return;

        dfs(root->left);

        if (pre == root->val)
            curc ++;
        else 
            curc = 1;
        pre = root->val;

        if (curc > maxc){
            maxc = curc;
            res = {pre};
        }

        else if (curc == maxc) res.push_back(pre);

        dfs(root->right);
    }
};

leetcode.701 二叉搜索树中的插入操作

  • 链接https://leetcode.cn/problems/insert-into-a-binary-search-tree/
  • 解题方法：
    递归函数功能：在 root 为根节点的二叉搜索树中插入 val
    1. 递归终止条件：如果根节点不存在，在新树根节点为 val
    2. 递归逻辑：
      如果 val 大于根节点的值，应该在右子树中插入 val
      同理，如果 val 小于根节点的值，应该在左子树中插入 val
    3. 递归返回值：返回新树的根节点
  • leetcode解题代码
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) return new TreeNode(val);

        if (root->val > val) root->left = insertIntoBST(root->left, val);
        else root->right = insertIntoBST(root->right, val);
        return root;
    }
};

leetcode.450 删除二叉搜索树中的节点

  • 链接https://leetcode.cn/problems/delete-node-in-a-bst/
  • 解题方法：
    递归函数功能：在 root 为根节点的二叉搜索树中删除 key
    1. 递归终止条件：如果根节点不存在，在新树根节点为 val
    2. 递归逻辑：
      如果 key 等于根节点的值，有以下四种可能：
      根节点为叶子节点，删除根节点后树的根节点为空
      根节点只有左儿子，删除根节点后树的根节点为左儿子
      根节点只有右儿子，删除根节点后树的根节点为右儿子
      根节点左右儿子都有，删除根节点后树的根节点为右儿子，并且将左儿子接到右子树的左下角
      如果 key 大于根节点的值，应该在右子树中删除 key，右子树的根节点为 root->right
      如果 key 小于根节点的值，应该在左子树中删除 key，左子树的根节点为 root->left
    3. 递归返回值：返回删除 key 后树的根节点
  • 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:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;

        if (key == root->val){
            if (!root->left && !root->right) return nullptr;
            else if (root->left && !root->right) return root->left;
            else if (!root->left && root->right) return root->right;
            else {
                auto cur = root->right;
                while (cur->left)
                    cur = cur->left;
                cur->left = root->left;
                return root->right;
            }
        }
        else if (key > root->val) 
            root->right = deleteNode(root->right, key);
        else 
            root->left = deleteNode(root->left, key);
        return root;
    }
};

leetcode.669 修剪二叉搜索树

  • 链接https://leetcode.cn/problems/trim-a-binary-search-tree/
  • 解题方法：
    递归函数功能：修剪二叉搜索树使得二叉搜索树中所有的节点都在[low, high] 之间
    1. 递归终止条件：如果根节点不存在，满足条件的根节点为空
    2. 递归逻辑：
      如果根节点的值小于 low 的值，说明符合条件的根节点在右子树中，在右子树中找，返回的即为新的根节点
      如果根节点的值大于 high 的值，说明符合条件的根节点在左子树中，在左子树中找，返回的即为新的根节点
      找到了根节点，递归构造新的左右子树
    3. 递归返回值：返回满足条件的树的根节点
  • leetcode解题代码
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (!root) return NULL;

        if (root->val < low) return trimBST(root->right, low, high);
        if (root->val > high) return trimBST(root->left, low, high);
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);

        return root;
    }
};

leetcode.538 把二叉搜索树转换为累加树

  • 链接https://leetcode.cn/problems/convert-bst-to-greater-tree/
  • 解题方法：
    递归函数功能：构造新树，将所有大于等于根节点的值累加到根节点上
    1. 递归终止条件：如果根节点不存在，满足条件的根节点为空
    2. 递归逻辑：
      二叉搜索树所有大于等于根节点的值都在右子树中，将所有右子树的值累加并更新到根节点上，再递归左子树
    3. 递归返回值：返回新树的根节点
  • 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:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        if (!root) return nullptr;

        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        convertBST(root->left);
        return root;
    }
};

leetcode.235 二叉搜索树的最近公共祖先

  • 链接https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
  • 解题方法：
    递归函数功能：找 p，q 的最近公共祖先节点
    1. 递归终止条件：如果 p，q 两个节点一个在左子树一个在右子树则最近公共祖先为根节点
    2. 递归逻辑：
      如果两个节点的值都小于根节点说明最近公共祖先在左子树，否则在右子树
  • leetcode解题代码
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if ((long)(root->val - p->val) * (root->val - q->val) <= 0) return root;
        if (root->val > p->val && root->val > q->val) return lowestCommonAncestor(root->left, p, q);
        return lowestCommonAncestor(root->right, p, q);
    }
};