欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode—树—BST

程序员文章站 2022-03-13 13:41:17
...

LeetCode—树—BST

二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。

二叉查找树中序遍历有序。

1、修剪二叉查找树
T669. Trim a Binary Search Tree (Easy)
LeetCode—树—BST

/**
 * 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* trimBST(TreeNode* root, int L, int R) {
        if(!root) return NULL;
        if(root->val < L)  return trimBST(root->right, L, R);
        if(root->val > R)  return trimBST(root->left, L, R);
        root->left = trimBST(root->left, L, R);
        root->right = trimBST(root->right, L, R);
        return root;

    }
};

2、寻找二叉查找树的第 k 个元素
T230. Kth Smallest Element in a BST (Medium)
LeetCode—树—BST

/**
 * 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 kthSmallest(TreeNode* root, int k) {
        int cnt = 0;
        stack<TreeNode*> s{{root}};
        TreeNode* p = root;
        while(p || !s.empty()){
            while(p){
                s.push(p);
                p=p->left; 
            }           
            p = s.top();
            s.pop();
            ++cnt;
            if(cnt == k)  return p->val;
            p = p->right;
        }
        return 0;
        
        
    }
};

3、把二叉查找树每个节点的值都加上比它大的节点的值
T538 Convert BST to Greater Tree (Easy)
LeetCode—树—BST

/**
 * 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* convertBST(TreeNode* root) {
        int sum=0;
        helper(root, sum);
        return root;

    }
    void helper(TreeNode*& node, int & sum){
        if(!node) return;
        helper(node->right, sum);
        node->val += sum;
        sum = node->val;
        helper(node->left, sum);
    }
};

4、二叉查找树的最近公共祖先
T235. Lowest Common Ancestor of a Binary Search Tree (Easy)
LeetCode—树—BST

/**
 * 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(!root) return NULL;
        if(root->val > max(p->val, q->val)){
            return lowestCommonAncestor(root->left, p, q);
        }
        else if(root->val < min(p->val, q->val)){
            return lowestCommonAncestor(root->right, p, q);
        }
        else return root;

        
    }
};

5、二叉树的最近公共祖先
T236. Lowest Common Ancestor of a Binary Tree (Medium)
LeetCode—树—BST

/**
 * 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(!root || p==root || q==root)  return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right= lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;
        return left ? left : right;
        
    }
};

6、从有序数组中构造二叉查找树
T108. Convert Sorted Array to Binary Search Tree (Easy)
LeetCode—树—BST

/**
 * 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* sortedArrayToBST(vector<int>& nums) {
        return helper(nums, 0, (int)nums.size() -1);

    }
    TreeNode* helper(vector<int>& nums, int left, int right){
        if(left > right) return NULL;
        int mid = left + (right-left) / 2;
        TreeNode* cur = new TreeNode(nums[mid]);
        cur->left = helper(nums, left, mid-1);
        cur->right = helper(nums, mid+1, right);
        return cur;
    }
};

7、根据有序链表构造平衡的二叉查找树
T109. Convert Sorted List to Binary Search Tree (Medium)
LeetCode—树—BST

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * 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* sortedListToBST(ListNode* head) {
        if(!head)  return NULL;
        if(!head->next)  return new TreeNode(head->val);
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* last = slow;
        while(fast->next && fast->next->next){
            last = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        last->next = NULL;
        TreeNode* cur = new TreeNode(slow->val);
        if(head != slow) cur->left = sortedListToBST(head);
        cur->right = sortedListToBST(fast);
        return cur;

        
    }
};

8、在二叉查找树中寻找两个节点,使它们的和为一个给定值
T653. Two Sum IV - Input is a BST (Easy)
LeetCode—树—BST

/**
 * 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:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> st;
        return helper(root, k, st);
    }
    bool helper(TreeNode* node, int k, unordered_set<int>& st){
        if(!node)  return false;
        if(st.count(k-node->val))  return true;
        st.insert(node->val);
        return helper(node->left, k, st) || helper(node->right, k, st);
    }
};

9、在二叉查找树中查找两个节点之差的最小绝对值
T530. Minimum Absolute Difference in BST (Easy)
LeetCode—树—BST

/**
 * 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:
    int getMinimumDifference(TreeNode* root) {
        int res = INT_MAX;
        int pre = -1;
        inorder(root, pre, res);
        return res;

    }
    void inorder(TreeNode* root, int& pre, int& res){
        if(!root)  return;
        inorder(root->left, pre, res);
        if(pre != -1)  res = min(res, root->val - pre);
        pre = root->val;
        inorder(root->right, pre, res);
    }
};

10、寻找二叉查找树中出现次数最多的值
T501. Find Mode in Binary Search Tree (Easy)
LeetCode—树—BST

/**
 * 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:
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        int mx = 0;
        unordered_map<int, int> m;
        inorder(root, m, mx);
        for(auto a : m){
            if(a.second == mx){
                res.push_back(a.first);
            }
        }
        return res;

    }
    void inorder(TreeNode* node, unordered_map<int, int>& m, int& mx){
        if(!node)  return;
        inorder(node->left, m, mx);
        mx = max(mx, ++m[node->val]);
        inorder(node->right, m, mx);
    }

};