seo交互论坛_免费素材哪个网站比较好_seo常用分析的专业工具_aso如何优化

代码随想录算法训练营

—day21

---

前言

今天是算法营的第21天，希望自己能够坚持下来！
今日任务：
● 669. 修剪二叉搜索树
● 108. 将有序数组转换为二叉搜索树
● 538. 把二叉搜索树转换为累加树

---

一、669. 修剪二叉搜索树

题目链接
文章讲解
视频讲解

修剪过程如下：

节点0不符合范围，只需要删除节点0，将节点0的右子树赋值给节点3的左子树就可以了：

递归法

思路：

1. 递归函数的参数和返回值：参数：当前传入节点和范围值。 返回值：修剪过后的根节点。
2. 终止条件：遇到空节点为止
3. 单层递归的逻辑：当前节点小于low，则左子树都会小于low，应该递归右子树，寻找能够当新节点的节点，并返回给上层；
4. 当前节点大于high，则右子树都会大于high，应该递归左子树，寻找能当新节点的头节点，并返回给上层。
5. 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;}
};

迭代法

因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。

在剪枝的时候，可以分为三步：

1. 将root移动到[L, R] 范围内，注意是左闭右闭区间
2. 剪枝左子树
3. 剪枝右子树

代码如下：

/*** 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的前一个节点，这样才方便做累加。
思路：

1. 递归函数的参数和返回值：传入树的根节点，不需要返回值
2. 终止条件：遇空就终止。
3. 单层递归的逻辑：注意要右中左来遍历二叉树， 中节点的处理逻辑就是让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.单层递归逻辑
• 二叉树的遍历方式：前序遍历（中左右），中序遍历（左中右），后序遍历（左右中）
• 二叉树的迭代法，前序和后序相似，使用栈来存放需要处理的节点；而中序的栈是存放指针访问的节点，向左访问到最底层，再弹出节点进行处理，再向右访问。
• 统一迭代法则是使用在需要处理的节点（中间节点）后面再放入空指针用来标记这是需要处理的节点，只有遇到空节点弹出时，才进行处理下一个节点
• 二叉树的层序遍历：用队列模拟实现
• 涉及到二叉树的构造，无论普通二叉树还是二叉搜索树一定前序，都是先构造中节点。
• 求普通二叉树的属性，一般是后序，一般要通过递归函数的返回值做计算。
• 求二叉搜索树的属性，一定是中序了，要不白瞎了有序性了。

下面是其他星球成员做的图，借用一下：

明天继续加油！