669. 修剪二叉搜索树 - 力扣（LeetCode）
思路:
- 使用递归法，先找到在区间内的节点作为根节点，方法是让此时的根节点与
low或者high比较，如果root->val < low，则要去左子树继续找，否则去右子树继续找。若一直未找到符合区间的值，则最终返回nullptr，若找到了，则将该根节点的左子树和右子树分别用同样方法进行修剪，最终返回的root即为修剪完成的二叉树 - 要注意的是，本题与450. 删除二叉搜索树中的节点 - 力扣（LeetCode）不同，那道题只是删除单独的节点，而本题是一个区间，如果不符合条件可以将整个子树都去掉
我的AC代码
//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int low, int high) {
if(root == nullptr) {
return nullptr;
}
if(root->val < low) {
return deleteNode(root->right, low, high);
}
else if(root->val > high) {
return deleteNode(root->left, low, high);
}
root->left = deleteNode(root->left, low, high);
root->right = deleteNode(root->right, low, high);
return root;
}
TreeNode* trimBST(TreeNode* root, int low, int high) {
return deleteNode(root, low, high);
}
};标准答案
递归法
//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr ) return nullptr;
if (root->val < low) {
TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
return right;
}
if (root->val > high) {
TreeNode* left = trimBST(root->left, low, high); // 寻找符合区间[low, high]的节点
return left;
}
root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
return root;
}
};迭代法
//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int L, int R) {
if (!root) return nullptr;
// 处理头结点，让root移动到[L, R] 范围内，注意是左闭右闭
while (root != nullptr && (root->val < L || root->val > R)) {
if (root->val < L) root = root->right; // 小于L往右走
else root = root->left; // 大于R往左走
}
TreeNode *cur = root;
// 此时root已经在[L, R] 范围内，处理左孩子元素小于L的情况
while (cur != nullptr) {
while (cur->left && cur->left->val < L) {
cur->left = cur->left->right;
}
cur = cur->left;
}
cur = root;
// 此时root已经在[L, R] 范围内，处理右孩子大于R的情况
while (cur != nullptr) {
while (cur->right && cur->right->val > R) {
cur->right = cur->right->left;
}
cur = cur->right;
}
return root;
}
};108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
思路:
- 思路和已知前中序遍历结果或者已知后中序遍历结果构造唯一二叉树类似，先找到中间节点，即数组的中间，然后以此为分界线将数组分割为左右两份，左边是左子树，右边是右子树，它们的根节点依然是中间部分，左右区间都递归完成即构造完成
我的AC代码
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
TreeNode* build(vector<int>& nums, int nbegin, int nend) {
int nsize = nend - nbegin;
if(nsize <= 0) {
return nullptr;
}
int sign = (nend + nbegin) / 2;
TreeNode* root = new TreeNode(nums[sign]);
if(nsize == 1) {
return root;
}
int lbegin = nbegin;
int lend = sign;
int rbegin = sign + 1;
int rend = nend;
root->left = build(nums, lbegin, lend);
root->right = build(nums, rbegin, rend);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size());
}
};标准答案
递归
//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};迭代法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0) return nullptr;
TreeNode* root = new TreeNode(0); // 初始根节点
queue<TreeNode*> nodeQue; // 放遍历的节点
queue<int> leftQue; // 保存左区间下标
queue<int> rightQue; // 保存右区间下标
nodeQue.push(root); // 根节点入队列
leftQue.push(0); // 0为左区间下标初始位置
rightQue.push(nums.size() - 1); // nums.size() - 1为右区间下标初始位置
while (!nodeQue.empty()) {
TreeNode* curNode = nodeQue.front();
nodeQue.pop();
int left = leftQue.front(); leftQue.pop();
int right = rightQue.front(); rightQue.pop();
int mid = left + ((right - left) / 2);
curNode->val = nums[mid]; // 将mid对应的元素给中间节点
if (left <= mid - 1) { // 处理左区间
curNode->left = new TreeNode(0);
nodeQue.push(curNode->left);
leftQue.push(left);
rightQue.push(mid - 1);
}
if (right >= mid + 1) { // 处理右区间
curNode->right = new TreeNode(0);
nodeQue.push(curNode->right);
leftQue.push(mid + 1);
rightQue.push(right);
}
}
return root;
}
};538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
思路:
- 方法一：遍历两次二叉搜索树，第一次算出二叉搜索树所有节点值的和
sum，第二次遍历的时候每遇到一个节点先将sum的值赋给该节点，然后再执行sum -= 节点->val - 方法二：反中序遍历二叉搜索树，累加节点值
我的AC代码
遍历两次
//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
int sum = 0;
void travel_1(TreeNode* root) {
if(root == nullptr) {
return;
}
travel_1(root->left);
sum += root->val;
travel_1(root->right);
}
TreeNode* travel_2(TreeNode* root, int& sum) {
if(root == nullptr) {
return nullptr;
}
travel_2(root->left, sum);
int tmp = root->val;
root->val = sum;
sum-= tmp;
travel_2(root->right, sum);
return root;
}
TreeNode* convertBST(TreeNode* root) {
if(root == nullptr) {
return nullptr;
}
travel_1(root);
return travel_2(root, sum);
}
};标准答案
反中序遍历递归法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
int pre = 0; // 记录前一个节点的数值
void traversal(TreeNode* cur) { // 右中左遍历
if (cur == NULL) return;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};迭代法
//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
int pre; // 记录前一个节点的数值
void traversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur != NULL || !st.empty()) {
if (cur != NULL) {
st.push(cur);
cur = cur->right; // 右
} else {
cur = st.top(); // 中
st.pop();
cur->val += pre;
pre = cur->val;
cur = cur->left; // 左
}
}
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};
Comments NOTHING