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;
}
};