資訊專欄INFORMATION COLUMN
??給你一棵二叉搜索樹，請(qǐng)按 中序遍歷 將其重新排列為一棵遞增順序搜索樹，使樹中最左邊的節(jié)點(diǎn)成為樹的根節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)沒有左子節(jié)點(diǎn)，只有一個(gè)右子節(jié)點(diǎn)。
??樣例輸入：[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）根據(jù) 中序遍歷 的思路，左子樹遍歷完，遍歷根，再遍歷右子樹。加上二叉搜索樹的性質(zhì)，左子樹所有元素 一定小于 根元素，右子樹所有元素 一定大于 根元素；
??2）對(duì)于 左子樹，需要返回一個(gè) 值最小 的結(jié)點(diǎn)，讓它指向 根結(jié)點(diǎn)；對(duì)于 右子樹，需要返回一個(gè) 值最大 的結(jié)點(diǎn)，并且讓 根結(jié)點(diǎn) 的right指針指向它；
??3）基于上述幾個(gè)點(diǎn)，需要提供一個(gè)函數(shù)，返回一顆子樹的 最小結(jié)點(diǎn) 和 最大結(jié)點(diǎn)。
?? 這是一個(gè)遍歷整棵樹的過程，每個(gè)結(jié)點(diǎn)訪問一次，時(shí)間復(fù)雜度為 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都為這個(gè)根結(jié)點(diǎn)；right指向當(dāng)前根結(jié)點(diǎn)；right指向 右子樹最小結(jié)點(diǎn)的；??二叉樹的 中序遍歷 是指：左子樹遍歷完，遍歷根，再遍歷右子樹。
??相信看我文章的大多數(shù)都是「 大學(xué)生 」，能上大學(xué)的都是「 精英 」，那么我們自然要「 精益求精 」，如果你還是「 大一 」，那么太好了，你擁有大把時(shí)間，當(dāng)然你可以選擇「 刷劇 」，然而，「 學(xué)好算法 」，三年后的你自然「 不能同日而語 」。
??那么這里，我整理了「 幾十個(gè)基礎(chǔ)算法 」 的分類，點(diǎn)擊開啟：
??大致題集一覽：
??為了讓這件事情變得有趣，以及「 照顧初學(xué)者 」，目前題目只開放最簡(jiǎn)單的算法 「 枚舉系列 」 （包括：線性枚舉、雙指針、前綴和、二分枚舉、三分枚舉），當(dāng)有 一半成員刷完 「 枚舉系列 」 的所有題以后，會(huì)開放下個(gè)章節(jié)，等這套題全部刷完，你還在群里，那么你就會(huì)成為「 夜深人靜寫算法 」專家團(tuán) 的一員。
??不要小看這個(gè)專家團(tuán)，三年之后，你將會(huì)是別人 望塵莫及 的存在。如果要加入，可以聯(lián)系我，考慮到大家都是學(xué)生， 沒有「 主要經(jīng)濟(jì)來源 」，在你成為神的路上，「 不會(huì)索取任何 」。
???聯(lián)系作者，或者掃作者主頁二維碼加群，加入刷題行列吧?
?讓天下沒有難學(xué)的算法?
C語言免費(fèi)動(dòng)漫教程，和我一起打卡！ ?《光天化日學(xué)C語言》?
入門級(jí)C語言真題匯總 ?《C語言入門100例》?
幾張動(dòng)圖學(xué)會(huì)一種數(shù)據(jù)結(jié)構(gòu) ?《畫解數(shù)據(jù)結(jié)構(gòu)》?
組團(tuán)學(xué)習(xí)，抱團(tuán)生長(zhǎng) ?《算法入門指引》?
競(jìng)賽選手金典圖文教程 ?《夜深人靜寫算法》?
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/119807.html
摘要：解法一中序遍歷分析由于給定了二叉搜索樹，因此首先考慮中序遍歷，使用示例，我們先來分別看一下二叉搜索樹和累加樹中序遍歷的結(jié)果二叉搜索樹二叉累加樹。這里還是使用示例，我們?cè)賮碛^察一下二叉搜索樹和累加樹中序遍歷的結(jié)果二叉搜索樹二叉累加樹。 ...
摘要：也就是說，有個(gè)節(jié)點(diǎn)的平衡二叉搜索樹，它的高度是。以搜索操作為例，如果二叉搜索樹的高度為，則時(shí)間復(fù)雜度為。二叉搜索樹的高度的確很重要。樹集合，中的或者中的，是由高度平衡的二叉搜索樹實(shí)現(xiàn)的。 ...
摘要：根據(jù)這個(gè)特征，用二分法來將有序數(shù)組轉(zhuǎn)換為一顆二叉搜索樹。邊界條件向下取整得到中間值遞歸二分法接下來我們驗(yàn)證下一棵樹是否滿足二叉搜索樹。二驗(yàn)證二叉搜索樹相關(guān)題目驗(yàn)證二叉搜索樹中等思路就是，中序遍歷如果滿足遞增的就行。 二叉樹大家都知道，二叉搜索樹滿足以下特征： 節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù) 所有左子樹和右子樹自身必須也是二叉搜索樹 二叉搜索樹也叫...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
閱讀 2086·2023-04-25 19:03
閱讀 1237·2021-10-14 09:42
閱讀 3419·2021-09-22 15:16
閱讀 1003·2021-09-10 10:51
閱讀 1585·2021-09-06 15:00
閱讀 2411·2019-08-30 15:55
閱讀 492·2019-08-29 16:22
閱讀 901·2019-08-26 13:49
