恢復(fù)二叉搜索樹(shù)

題目描述：給你二叉搜索樹(shù)的根節(jié)點(diǎn) root ，該樹(shù)中的兩個(gè)節(jié)點(diǎn)被錯(cuò)誤地交換。請(qǐng)?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹(shù)。

進(jìn)階：使用 O(n) 空間復(fù)雜度的解法很容易實(shí)現(xiàn)。你能想出一個(gè)只使用常數(shù)空間的解決方案嗎？

示例說(shuō)明請(qǐng)見(jiàn)LeetCode官網(wǎng)。

來(lái)源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/recover-binary-search-tree/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：遞歸法

• 首先，通過(guò)中序遍歷得到二叉搜索樹(shù)的所有節(jié)點(diǎn)allNodes，正常情況下，如果沒(méi)有節(jié)點(diǎn)被錯(cuò)誤的交換，allNodes所有節(jié)點(diǎn)應(yīng)該是按升序排列，所以要找出被交換的2個(gè)節(jié)點(diǎn)；

• 從后往前遍歷allNodes，找到第一個(gè)值比前面的值小的節(jié)點(diǎn)，即為錯(cuò)誤的第一個(gè)節(jié)點(diǎn)high；

• 從high-1開(kāi)始往前遍歷allNodes，找到第一個(gè)值比high節(jié)點(diǎn)小的節(jié)點(diǎn)low，low+1位置的節(jié)點(diǎn)即為錯(cuò)誤的第二個(gè)節(jié)點(diǎn)；

• 交換low和high2個(gè)節(jié)點(diǎn)的值，即可恢復(fù)這棵樹(shù)。

【每日寄語(yǔ)】 感謝不離不棄的你，讓我知道仍有人愛(ài)我。感謝你的支持，不論今天有多挫折，我仍會(huì)勇敢地活下去。