LeetCode—树—BST
LeetCode—树—BST
二叉查找树(BST):根节点大于等于左子树所有节点,小于等于右子树所有节点。
二叉查找树中序遍历有序。
1、修剪二叉查找树
T669. Trim a Binary Search Tree (Easy)
/**
* 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)
/**
* 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)
/**
* 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)
/**
* 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)
/**
* 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)
/**
* 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)
/**
* 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)
/**
* 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)
/**
* 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)
/**
* 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);
}
};
下一篇: 螺旋方阵