前言
本周終于完成了一道困難題Ｉ纸酢！剧包！
恢復(fù)二叉搜索樹
二叉搜索樹中的兩個(gè)節(jié)點(diǎn)被錯(cuò)誤地交換。
請?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下往果，恢復(fù)這棵樹疆液。
示例 1:
示例 2:
題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/recover-binary-search-tree
先放我的代碼：
/**
* 力扣中關(guān)于二叉樹的默認(rèn)定義
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
TreeNode one = null; //逆序中大的值
TreeNode two = null; //逆序中小的值
TreeNode pre = null; //上一個(gè)節(jié)點(diǎn)
int temp;
public void recoverTree(TreeNode root) {
order(root); //中序遍歷找出逆序的兩個(gè)數(shù)
temp = one.val;
one.val = two.val;
two.val = temp;
}
public void order(TreeNode root){
if(root==null) return;
if(root.left!=null){
order(root.left);
}
if(pre!=null && pre.val > root.val){
if(one==null){
one=pre;
two=root;
}
else{
two=root;
}
}
pre=root;
if(root.right!=null){
order(root.right);
}
}
}
又是一道二叉樹問題，做了幾道后發(fā)現(xiàn)二叉樹問題一般都是可以用遞歸解決的陕贮，所以思路就很明確了堕油，遞歸！飘蚯！
通過之前對二叉樹的了解我知道了二叉樹的遍歷有：
先序遍歷馍迄，中序遍歷，后序遍歷局骤，層次遍歷攀圈。
而題目又說的很明確，二叉搜索樹Ｂ退Α赘来！對于二叉搜索樹，百度百科有很清晰的解釋：
這樣的話解法就很清晰了凯傲，中序遍歷+遞歸犬辰。先遞歸到最小的一個(gè)節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)開始判斷冰单，若這個(gè)節(jié)點(diǎn)前一個(gè)數(shù)大于當(dāng)前節(jié)點(diǎn)就說明有沖突幌缝，這兩個(gè)數(shù)就是我們要找的數(shù)了。然鵝夢想是美好的現(xiàn)實(shí)是殘酷的诫欠，沒這么簡單涵卵，我的想法僅限于相鄰的兩個(gè)數(shù)之間的交換浴栽，不得已看了一下官方題解，發(fā)現(xiàn)兩個(gè)數(shù)沖突叫做逆序轿偎，而這個(gè)逆序有兩種可能性典鸡，一種是相鄰之間的逆序，一種是相隔幾個(gè)數(shù)的逆序坏晦，前者會(huì)產(chǎn)生一組逆序的數(shù)字萝玷，后者會(huì)產(chǎn)生兩組逆序的數(shù)組，因此需要在逆序那里多加一次判斷昆婿，第一次逆序時(shí)把one賦給pre球碉，也就是較大的值，root賦給two挖诸；第二次逆序時(shí)把root再次賦給two汁尺。如此一來法精，可以確保one里面存的就是大的那個(gè)數(shù)多律，two存的是小數(shù)。退出遞歸后
recoverTree方法僅僅是把one.val和two.val交換即可恢復(fù)二叉搜索樹搂蜓。歡迎訪問我的博客www.redmango.top
