06二叉搜索树的操作
# 06 二叉搜索树的操作
# 669 修剪二叉搜索树 (opens new window)
给定一个二叉查找树和两个整数 L 和 R,且 L < R,试修剪此二叉查找树,使得修剪后所有节点的值都在 [L, R] 的范围内。
输入是一个二叉查找树和两个整数 L 和 R,输出一个被修剪好的二叉查找树。
输入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输出:[3,2,null,1]
解析:
利用二叉查找树的大小关系,我们可以很容易地利用递归进行树的处理。
递归遍历每一个节点,如果当前值大于 high 那么修剪后的二叉树必定出现在节点的左边;如果当前值小于 low 那么修剪后的二叉树出现在节点的右边;如果当前节点值在区间内,则往左右子树递归。
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(!root){
return root;
}
// 当前值大于 high 那么修剪后的二叉树必定出现在节点的左边
if(root->val > high){
return trimBST(root->left,low,high);
}
// 当前值小于 low 那么修剪后的二叉树出现在节点的右边
if(root->val < low){
return trimBST(root->right,low,high);
}
// 当前值在区间内,则往左右子树递归
root->left = trimBST(root->left,low,high);
root->right = trimBST(root->right,low,high);
return root;
}
};
# 99 恢复二叉搜索树 (opens new window)
给定一个二叉搜索树,已知有两个节点被不小心交换了,试复原此树
输入是一个被误交换两个节点的二叉搜索树,输出是改正后的二叉搜索树
输入:root = [3,1,4,null,null,2] 输出:[2,1,4,null,null,3] 解释:2 不能在 3 的右子树中,因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
解析:
本题没搞懂,有待深究
使用中序遍历一棵二叉搜索树,得到的遍历结果是节点值递增的序列,利用二叉搜索树这一特点可以快速找出错误的节点。
得到二叉搜索树的中序遍历序列,找到错误的节点,交换两个节点的值。
class Solution {
public:
void inorder(TreeNode* root, vector<int>& nums) {
if (root == nullptr) {
return;
}
inorder(root->left, nums);
nums.push_back(root->val);
inorder(root->right, nums);
}
pair<int,int> findTwoSwapped(vector<int>& nums) {
int n = nums.size();
int index1 = -1, index2 = -1;
for (int i = 0; i < n - 1; ++i) {
if (nums[i + 1] < nums[i]) {
index2 = i + 1;
if (index1 == -1) {
index1 = i;
} else {
break;
}
}
}
int x = nums[index1], y = nums[index2];
return {x, y};
}
void recover(TreeNode* r, int count, int x, int y) {
if (r != nullptr) {
if (r->val == x || r->val == y) {
r->val = r->val == x ? y : x;
if (--count == 0) {
return;
}
}
recover(r->left, count, x, y);
recover(r->right, count, x, y);
}
}
void recoverTree(TreeNode* root) {
vector<int> nums;
inorder(root, nums);
pair<int,int> swapped= findTwoSwapped(nums);
recover(root, 2, swapped.first, swapped.second);
}
};
# 109 有序链表转换二叉搜索树 (opens new window)
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
输入一个链表,输出一个左右子树高度差不超过1的平衡二叉搜索树
给定的有序链表: [-10, -3, 0, 5, 9],
一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:
0 / \ -3 9 / / -10 5
解析:
要保证平衡,那么需要寻找链表的中点,以中点为根节点构造二叉树,小于中点的元素组成左子树,大于中点的元素组成右子树,它们分别对应着有序链表中连续的一段,这就保证了左右子树节点数目之差不超过1,从而实现二叉树的平衡。
在这之后,我们使用分治的思想,继续递归地对左右子树进行构造,找出对应的中点作为根节点,直到构造叶子节点完成时返回。
寻找链表中点的一种常见方式就是快慢指针,快指针和慢指针在同一节点出发,快指针一次走两步,慢指针一次走一步,当快指针到达终点时,慢指针指向的就是链表中点。注意循环条件,本题在递归过程中,子树对应的链表最后一个节点的next
不一定是nullptr
。
找到链表中点之后,构造该节点,并递归构造其左右节点。
class Solution {
public:
ListNode* getMid(ListNode* left, ListNode* right){
ListNode* fast = left;
ListNode* slow = left;
// 注意判断条件,终止条件是右边接而不是 nullptr
while(fast != right && fast->next != right){
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
TreeNode* buildTree(ListNode* left, ListNode* right){
if(left == right){
return nullptr;
}
ListNode* midNode = getMid(left,right);
TreeNode* root = new TreeNode(midNode->val);
root->left = buildTree(left,midNode);
root->right = buildTree(midNode->next,right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
// 链表的右边界是nullptr
return buildTree(head,nullptr);
}
};
每次构造节点都需要使用快慢指针遍历链表寻找中点,这极大地耗损了算法效率。由于构造出的二叉搜索树的中序遍历结果就是链表本身,我们可以采用中序遍历思路减少时间复杂度。
中序遍历的顺序是「左子树 - 根节点 - 右子树」,那么在分治的过程中,我们不用急着找出链表的中位数节点,而是使用一个占位节点,等到中序遍历到该节点时,再填充它的值。
在中序序列中,假设左端点编号为left,右端点编号为right,那么根节点就是 mid = (left+right+1)/2 或者是 mid = (left+right)/2 ,左子树节点范围为 [left, mid-1],右子树节点范围为 [mid+1,right]。根据中序遍历结果恢复二叉搜索树。
class Solution {
public:
TreeNode* buildTreeMid(ListNode*& head, int left, int right){
if(left > right){
return nullptr;
}
int mid = (left+right+1)/2;
TreeNode* root = new TreeNode();
root->left = buildTreeMid(head,left,mid-1);
root->val = head->val;
head = head->next; // 不懂为什么要传引用,而不可以直接传实参
root->right = buildTreeMid(head,mid+1,right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
int len = 0;
ListNode* cur = head;
while(cur){
++len;
cur = cur->next;
}
return buildTreeMid(head,0,len-1);
}
};
# 450 删除二叉搜索树中的节点 (opens new window)
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。
输入一个二叉搜索树和待删除节点值 key,输入一个删除节点key后的二叉搜索树
输入:root = [5,3,6,2,4,null,7], key = 3 输出:[5,4,6,2,null,null,7] 解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。一个正确的答案是 [5,4,6,2,null,null,7]
解析:
1. 找到需要删除的节点
利用二叉搜索树特性,递归查找待删除节点。如果当前节点值小于 key 那么往其右子树递归查找,如果当前节点值大于 key 那么往其左子树递归查找,如果相等就开始删除操作。
2. 删除的节点
删除节点要区分四种情况:当前节点是叶节点、只有左子节点、只有右子节点和有两个子节点
- 当前节点是叶节点:直接删除节点, 返回NULL为根节点、
- 当前节点只有左子节点:删除节点,左孩子补位,返回左孩子为根节点
- 当前节点只有右子节点:删除节点,右孩子补位,返回右孩子为根节点
- 当前节点有两个子节点:将当前节点的左子树整体移动到其右子树的最左侧节点的左节点上,返回删除节点右节点为新的根节点
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root){
return root;
}
if(root->val == key){
// 叶子节点
if(!root->left && !root->right){
delete root;
return nullptr;
}
// 只有左节点
else if(root->left && !root->right){
TreeNode* node = root->left;
delete root;
return node;
}
// 只有右节点
else if(!root->left && root->right){
TreeNode* node = root->right;
delete root;
return node;
}
// 有两个子节点
else{
TreeNode* cur = root->right;
while(cur->left){
cur = cur->left;
}
cur->left = root->left;
TreeNode* node = root->right;
delete root;
return node;
}
}
// 递归查找删除节点
if(root->val > key){
root->left = deleteNode(root->left,key);
}
if(root->val < key){
root->right = deleteNode(root->right,key);
}
return root;
}
};