给你一棵二叉搜索树，请按 中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
样例输入：[5,3,6,2,4,null,8,1,null,null,null,7,9]
样例输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
struct TreeNode* increasingBST(struct TreeNode* root){} 1）根据 中序遍历 的思路，左子树遍历完，遍历根，再遍历右子树。加上二叉搜索树的性质，左子树所有元素 一定小于 根元素，右子树所有元素 一定大于 根元素；
2）对于 左子树，需要返回一个 值最小 的结点，让它指向 根结点；对于 右子树，需要返回一个 值最大 的结点，并且让 根结点 的right指针指向它；
3）基于上述几个点，需要提供一个函数，返回一颗子树的 最小结点 和 最大结点。
这是一个遍历整棵树的过程，每个结点访问一次，时间复杂度为 O ( n ) O(n) O(n)。
void findMaxMin(struct TreeNode* root, struct TreeNode** min, struct TreeNode** max) { struct TreeNode* node = NULL; struct TreeNode* lmin, *lmax; struct TreeNode* rmin, *rmax; if( root == NULL ) { *min = *max = NULL; // (1) return ; } node = (struct TreeNode *) malloc ( sizeof(struct TreeNode) ); node->val = root->val; // (2) node->right = NULL; node->left = NULL; *min = *max = node; if(root->left) { // (3) findMaxMin(root->left, &lmin, &lmax); lmax->right = node; // (4) *min = lmin; } if(root->right) { // (5) findMaxMin(root->right, &rmin, &rmax); node->right = rmin; // (6) *max = rmax; }}struct TreeNode* increasingBST(struct TreeNode* root){ struct TreeNode* min; struct TreeNode* max; findMaxMin(root, &min, &max); return min;}min和max都不存在；min和max都为这个根结点；right指向当前根结点；right指向 右子树最小结点的；二叉树的 中序遍历 是指：左子树遍历完，遍历根，再遍历右子树。
相信看我文章的大多数都是「 大学生 」，能上大学的都是「 精英 」，那么我们自然要「 精益求精 」，如果你还是「 大一 」，那么太好了，你拥有大把时间，当然你可以选择「 刷剧 」，然而，「 学好算法 」，三年后的你自然「 不能同日而语 」。
那么这里，我整理了「 几十个基础算法 」 的分类，点击开启：
大致题集一览：
为了让这件事情变得有趣，以及「 照顾初学者 」，目前题目只开放最简单的算法 「 枚举系列 」 （包括：线性枚举、双指针、前缀和、二分枚举、三分枚举），当有 一半成员刷完 「 枚举系列 」 的所有题以后，会开放下个章节，等这套题全部刷完，你还在群里，那么你就会成为「 夜深人静写算法 」专家团 的一员。
不要小看这个专家团，三年之后，你将会是别人 望尘莫及 的存在。如果要加入，可以联系我，考虑到大家都是学生， 没有「 主要经济来源 」，在你成为神的路上，「 不会索取任何 」。
?联系作者，或者扫作者主页二维码加群，加入刷题行列吧?
?让天下没有难学的算法?
C语言免费动漫教程，和我一起打卡！ ?《光天化日学C语言》?
入门级C语言真题汇总 ?《C语言入门100例》?
几张动图学会一种数据结构 ?《画解数据结构》?
组团学习，抱团生长 ?《算法入门指引》?
竞赛选手金典图文教程 ?《夜深人静写算法》?
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/119807.html
分门别类刷算法，坚持，进步！ 刷题路线参考：https://github.com/youngyangyang04/leetcode-master 大家好，我是拿输出博客来督促自己刷题的老三，这一节我们来刷二叉树，二叉树相关题目在面试里非常高频，而且在力扣里数量很多，足足有几百道，不要慌，我们一步步来。我的文章很长，你们 收藏一下。 二叉树基础 二叉树是一种比较常见的数据结构，在开始刷二叉树...
摘要：解法一中序遍历分析由于给定了二叉搜索树，因此首先考虑中序遍历，使用示例，我们先来分别看一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。这里还是使用示例，我们再来观察一下二叉搜索树和累加树中序遍历的结果二叉搜索树二叉累加树。 ...
摘要：也就是说，有个节点的平衡二叉搜索树，它的高度是。以搜索操作为例，如果二叉搜索树的高度为，则时间复杂度为。二叉搜索树的高度的确很重要。树集合，中的或者中的，是由高度平衡的二叉搜索树实现的。 ...
摘要：根据这个特征，用二分法来将有序数组转换为一颗二叉搜索树。边界条件向下取整得到中间值递归二分法接下来我们验证下一棵树是否满足二叉搜索树。二验证二叉搜索树相关题目验证二叉搜索树中等思路就是，中序遍历如果满足递增的就行。 二叉树大家都知道，二叉搜索树满足以下特征： 节点的左子树只包含小于当前节点的数节点的右子树只包含大于当前节点的数 所有左子树和右子树自身必须也是二叉搜索树 二叉搜索树也叫...
摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。 这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。 在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...
阅读 1570·2023-04-25 19:03
阅读 1420·2021-11-24 09:39
阅读 1046·2021-10-14 09:42
阅读 3107·2021-09-29 09:32
阅读 3019·2021-09-22 15:16
阅读 771·2021-09-10 10:51
阅读 1255·2021-09-06 15:00
阅读 2214·2019-08-30 15:55
