代码随想录算法训练营day21
代码随想录算法训练营
—day21
文章目录
- 代码随想录算法训练营
- 前言
- 一、669. 修剪二叉搜索树
- 递归法
- 迭代法
- 二、108.将有序数组转换为二叉搜索树
- 递归法
- 迭代法
- 三、538.把二叉搜索树转换为累加树
- 递归法
- 总结
前言
今天是算法营的第21天，希望自己能够坚持下来！
今日任务：
● 669. 修剪二叉搜索树
● 108. 将有序数组转换为二叉搜索树
● 538. 把二叉搜索树转换为累加树
一、669. 修剪二叉搜索树
题目链接
文章讲解
视频讲解
修剪过程如下：
节点0不符合范围，只需要删除节点0，将节点0的右子树赋值给节点3的左子树就可以了：
递归法
思路：
- 递归函数的参数和返回值：参数：当前传入节点和范围值。 返回值：修剪过后的根节点。
- 终止条件：遇到空节点为止
- 单层递归的逻辑：当前节点小于low，则左子树都会小于low，应该递归右子树，寻找能够当新节点的节点，并返回给上层；
- 当前节点大于high，则右子树都会大于high，应该递归左子树，寻找能当新节点的头节点，并返回给上层。
- root的左节点和右节点分别接收由下层递归返回的修剪过的新节点。
/**
* 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:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) return nullptr; //遇到空节点返回
//当前节点大于阈值，向左递归寻找符合范围的节点
//当前节点小于阈值，向右递归寻找符合范围的节点
if (root->val > high) return trimBST(root->left, low, high);
else 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;
}
};
迭代法
因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。
在剪枝的时候，可以分为三步：
- 将root移动到[L, R] 范围内，注意是左闭右闭区间
- 剪枝左子树
- 剪枝右子树
代码如下：
/**
* 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:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if (root == nullptr) return nullptr;
//找到在[low,high]范围内的节点作为新的根节点
while (root!= nullptr && (root->val < low || root->val > high)) {
if (root->val < low) root = root->right;
else root = root->left;
}
//修剪左子树
TreeNode* cur = root;
while (cur != nullptr) {
while (cur->left && cur->left->val < low) {
cur->left = cur->left->right; //如果左节点不在范围内，则找左节点的右节点替换
}
cur = cur->left; //找到了合适的新左节点，继续循环判断新左节点的左节点是否合适
}
cur = root; //重新从根节点开始
while (cur != nullptr) {
while (cur->right && cur->right->val > high) { //如果右节点不在范围内，则找右节点的左节点替换
cur->right = cur->right->left;
}
cur = cur->right; //找到了合适的新右节点，继续循环判断新右节点的右节点是否合适
}
return root;
}
};
二、108.将有序数组转换为二叉搜索树
题目链接
文章讲解
视频讲解
递归法
思路：
取数组的中间元素作为根节点，然后递归左区间和右区间继续以区间中间元素作为中间节点，构建二叉树要使用中序遍历。
代码如下：
/**
* 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 {
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) {
if (nums.size() == 0) return nullptr;
return traversal(nums, 0, nums.size() - 1);
}
};
迭代法
迭代法可以通过三个队列来模拟，一个队列放遍历的节点，一个队列放左区间下标，一个队列放右区间下标。
代码如下：
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.把二叉搜索树转换为累加树
题目链接
文章讲解
视频讲解
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了。
换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]。
遍历顺序如图所示：
递归法
本题依然需要一个pre指针记录当前遍历节点cur的前一个节点，这样才方便做累加。
思路：
- 递归函数的参数和返回值：传入树的根节点，不需要返回值
- 终止条件：遇空就终止。
- 单层递归的逻辑：注意要右中左来遍历二叉树， 中节点的处理逻辑就是让cur的数值加上前一个节点的数值。
/**
* 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 pre = 0;
void traversal(TreeNode* node) {
if (node == nullptr) return;
traversal(node->right); //右
node->val += pre; //中，用pre记录上一个节点的值，与当前节点值累加
pre = node->val; //更新上一个节点值
traversal(node->left); //左
return;
}
//从题目的图中可看出，累加的顺序是右中左，所以反中序遍历二叉树，在用双指针依次累加即可
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};
总结
二叉树终于结束了！来个总结：
- 二叉树的递归：1.确定递归函数的参数 2.确定终止条件 3.单层递归逻辑
- 二叉树的遍历方式：前序遍历（中左右），中序遍历（左中右），后序遍历（左右中）
- 二叉树的迭代法，前序和后序相似，使用栈来存放需要处理的节点；而中序的栈是存放指针访问的节点，向左访问到最底层，再弹出节点进行处理，再向右访问。
- 统一迭代法则是使用在需要处理的节点（中间节点）后面再放入空指针用来标记这是需要处理的节点，只有遇到空节点弹出时，才进行处理下一个节点
- 二叉树的层序遍历：用队列模拟实现
- 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
- 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
- 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。
下面是其他星球成员做的图，借用一下：
明天继续加油！