代码随想录算法训练营DAY23|C++二叉树Part.9|669.修建二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

本文主要是介绍代码随想录算法训练营DAY23|C++二叉树Part.9|669.修建二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 669.修建二叉搜索树
    • 递归法思路
    • 伪代码
    • CPP代码
  • 108.将有序数组转换为二叉搜索树
    • 递归伪代码
    • CPP代码
  • 538.把二叉搜索树转换为累加树
    • 思路
    • 递归伪代码
    • 递归CPP代码
    • 迭代法

669.修建二叉搜索树

力扣题目链接

文章讲解:669.修建二叉搜索树

视频讲解:你修剪的方式不对,我来给你纠正一下!| LeetCode:669. 修剪二叉搜索树

状态:这个最关键的点在于,删除结点之后应该如何接上去

递归法思路

本题中最关键的在于我们应该如何重构BST,其实跟我们之前讲的题目删除二叉树中的结点类似。

这题一定要画图模拟才能搞清楚。

伪代码

  • 确定递归函数的参数和返回值:本题中有返回值可以大大降低代码难度,因为我们可以通过递归函数的返回值移除结点。
TreeNode* trimBST(TreeNode* root, int low, int high)
  • 确定终止条件:修剪的操作并不是在终止条件上进行的,所以遇到空结点返回即可。
if (root == nullptr) return nullptr;
  • 单层递归逻辑

    • 如果root(当前结点)的元素小于low的数值,那么应该递归右子树,并返回右子树符合条件的头结点。
    if (root->val < low){TreeNode* right = trimBST(root->right, low, high);return right;
    }
    
    • 如果root(当前结点)的元素大于high,那么应该递归左子树,并返回左子树符合条件的头结点
    if (root->val > high){TreeNode* left = trimBST(root->left, low, high);return left
    }
    
    • 将下一层处理完左子树的结果赋值给root->left,处理完右子树的结果赋给root->right
    root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
    root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
    return root;
    

CPP代码

#整体代码
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;}
};
#精简代码
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if (root == nullptr) return nullptr;if (root->val < low) return trimBST(root->right, low, high);if (root->val > high) return trimBST(root->left, low, high);root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);return root;}
};

108.将有序数组转换为二叉搜索树

力扣题目链接

文章讲解:108.将有序数组转换为二叉搜索树

视频讲解:构造平衡二叉搜索树!| LeetCode:108.将有序数组转换为二叉搜索树

状态:easy模式,其实就是构造二叉树。但是其中的难点在于,如何保持平衡呢?

递归伪代码

  • 确定递归函数返回值和参数:无论是删除还是增加二叉树的结点,都是用递归函数的返回值来完成的,这样操作会比较方便

本题同理,依然用递归函数u的返回值来构造中结点的左右孩子。

在构造二叉树的时候尽量不要重新定义左右区间数组,而是用下标来操作原数组

//左闭右闭区间[left, right]
TreeNode* traversal(vector<int>& nums, int left, int right)

在这里,我们定义好了左闭右闭区间,为了遵守循环不变量原则,在不断分割的过程中也一定要坚持左闭右闭的原则

  • 确定递归终止条件

这里定义的是左闭右闭的区间,所以当区间left>right当时候,就是空结点了

if (left > right) return nullptr;
  • 确定单层递归逻辑

划分区间的时候,root的左孩子接住下一层左区间的构造结点,右孩子接住下一层右区间构造的结点。

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;

CPP代码

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

538.把二叉搜索树转换为累加树

力扣题目链接

文章讲解:538.把 二叉搜索树转换为累加树

视频讲解:普大喜奔!二叉树章节已全部更完啦!| LeetCode:538.把二叉搜索树转换为累加树

状态: 每个结点都把比他大的结点做一个相加成为新结点值。感觉真的是毫无头绪

思路

直接在二叉树上操作真的很难。但是如果转换思路成一个数组呢?

给定一个有序数组,我们要将这个数组变成累加数组。

也就是说数组上的每个位置,都把其前面位置做一个相加,瞬间就能变成一个送分题

就是一个有序数组[2, 5, 13],求从后到前的累加数组,也就是[20, 18, 13],是不是感觉这就简单了,这里我们对数组的操作要从后向前进行遍历。

那么如果反应到二叉搜索树呢?

我们用中序遍历的二叉搜索树是有序数组,那么我们进行一个反中序遍历,也就是遍历顺序为右中左,然后顺序累加即可。那么如何实现这一块代码呢?换个顺序即可

递归伪代码

  • 递归函数参数和返回值:在这里我们不需要任何会返回值了,最主要的任务就是遍历整颗树
int pre = 0;
void traversal (TreeNode* cur)
  • 确定终止条件
if (cur == NULL) return;
  • 单层递归逻辑

右中左遍历二叉树,中结点的处理逻辑就是让cur的数值加上前一个结点的数值。

traversal(cur->right); 
cur->cur += pre;
pre = cur->val;
traversal(cur->left;)

递归CPP代码

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

迭代法

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

这篇关于代码随想录算法训练营DAY23|C++二叉树Part.9|669.修建二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/903996

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�