LeetCode刷题笔记二叉树二叉搜索树的操作

编程入门行业动态更新时间:2024-10-26 01:25:23

669 修剪二叉搜索树

给定一个二叉查找树和两个整数 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 恢复二叉搜索树

给定一个二叉搜索树，已知有两个节点被不小心交换了，试复原此树

输入是一个被误交换两个节点的二叉搜索树，输出是改正后的二叉搜索树

输入：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 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

输入一个链表，输出一个左右子树高度差不超过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;// 注意判断条件，终止条件是右边接而不是 nullptrwhile(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) {// 链表的右边界是nullptrreturn 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 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 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;}
};