LeetCode-099-恢復(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ì)勇敢地活下去。
