Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
這個(gè)題我看到的想法是先把所有element in order走一遍悴了，然后存進(jìn)O(n) space的array. 然后排序。排序好以后重新建一個(gè)BST.
但是這種naive solution太暴力了翼雀，不知道該怎么優(yōu)化刹勃。
但是要做到constant space, 。。盼产。。不知道怎么搞勺馆。戏售。。難怪這題是Hard level...
我做的時(shí)候大概知道要keep reference of 兩個(gè)覺得不對勁的Node草穆。比如他比left 小 || 比right 大灌灾，這很明顯就不對。 但是我就算keep了兩個(gè)Node, 沒辦法交換呀悲柱，因?yàn)樾枰鋚arent才可以操控他們交換锋喜。還有就是我是不是還得save一個(gè)left or right告訴parent這是在左邊還是右邊。豌鸡。嘿般。
看完答案感覺傻逼了。涯冠。博个。原來根本不用交換node reference. 只要記錄node reference，交換value就好了功偿。
然后我開始寫代碼: 用pre-order的方式盆佣，只要left|| right 比root大/小， 就save it作為first/second
看上去好像很對械荷，但是問題非常明顯共耍。 當(dāng)碰到below case的時(shí)候，我只把0 keep as first.
然后到了leaf的時(shí)候吨瞎，因?yàn)闆]有l(wèi)eft, right 所以不會進(jìn)行判斷痹兜，然后就GG了。
所以看起來正確的姿勢還是得用In-order Traversal的方法颤诀。
發(fā)現(xiàn)In-order是第一步字旭，第二步最難的就是
if(first == null && root.val < prev.val)
? ? ? first = prev;
if (first!=null && root.val < prev.val)
? ? second = prev;
這個(gè)算法下，first這個(gè)東西一確立以后就不會再更改了崖叫。 但是second是會更改的遗淳，所以我們必須遍歷整個(gè)Tree。?
下面這個(gè)例子心傀，人眼看過去很明顯12比1大是ok的屈暗，1比10大不ok，10比1小不ok。
這個(gè)看過去养叛， 1比5大不ok种呐， 5 比1小不ok， 11比5小不ok弃甥，5比11大也不對爽室。
一開始First 定了是11，然后second是5. 看起來很有道理淆攻，這兩個(gè)確實(shí)好像被交換了肮之。但是繼續(xù)遍歷發(fā)現(xiàn)，1那個(gè)node 也不應(yīng)該比5小啊卜录， 這個(gè)時(shí)候second就換成了1. 意思是
? ? ? ? ? ? ? ? ? 小
? ? ? ? ?中
大
把 大和小兩個(gè)換一下戈擒， 中不需要變，整個(gè)樹的2 swapped 就找到了艰毒。
這道題只assume 改了兩個(gè)node筐高，如果改了更多的話，就會出錯(cuò)丑瞧。
比如這個(gè)：
