golang中怎么利用leetcode 恢復(fù)二叉搜索樹，很多新手對(duì)此不是很清楚，為了幫助大家解決這個(gè)難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

創(chuàng)新互聯(lián)公司是一家專注網(wǎng)站建設(shè)、網(wǎng)絡(luò)營(yíng)銷策劃、微信平臺(tái)小程序開發(fā)、電子商務(wù)建設(shè)、網(wǎng)絡(luò)推廣、移動(dòng)互聯(lián)開發(fā)、研究、服務(wù)為一體的技術(shù)型公司。公司成立10余年以來，已經(jīng)為上1000+成都被動(dòng)防護(hù)網(wǎng)各業(yè)的企業(yè)公司提供互聯(lián)網(wǎng)服務(wù)?，F(xiàn)在，服務(wù)的上1000+客戶與我們一路同行，見證我們的成長(zhǎng)；未來，我們一起分享成功的喜悅。

二叉搜索樹中的兩個(gè)節(jié)點(diǎn)被錯(cuò)誤地交換。

請(qǐng)?jiān)诓桓淖兤浣Y(jié)構(gòu)的情況下，恢復(fù)這棵樹。

示例 1:

輸入: [1,3,null,null,2]

   1
  /
 3
  \
   2

輸出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

輸入: [3,1,4,null,null,2]

 3
/ \
1   4
   /
  2

輸出: [2,1,4,null,null,3]

 2
/ \
1   4
   /
 3

進(jìn)階:

• 使用 O(n) 空間復(fù)雜度的解法很容易實(shí)現(xiàn)。

• 你能想出一個(gè)只使用常數(shù)空間的解決方案嗎？

解題思路：

1，二叉樹的性質(zhì)：左子樹<根<小于右子樹

2，如果中序遍歷二叉樹就能得到一個(gè)遞增的序列

3，由于只交換了兩個(gè)位置，假設(shè)這兩個(gè)位置為first，second，則first左邊小于first，右邊大于first，second的左邊都小于second，只需交換first，second位置即可

4，如何得到遞增序列？

   中序遍歷

5，用pre記錄中序遍歷的上一個(gè)位置，如果pre.val>cur.val說明pre的位置放錯(cuò)了，用first，second 記錄兩個(gè)位置，最好交換即可

6，注意，由于使用了全局指針，所以，使用前一定要初始化，否則結(jié)果很奇怪

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */var pre,first,second *TreeNode
func recoverTree(root *TreeNode)  {    pre=nil    first=nil    second =nil    midOrder(root) 
    temp:=first.Val    first.Val=second.Val    second.Val=temp       return}
func midOrder(cur *TreeNode){    if cur==nil{        return    }    midOrder(cur.Left)    if pre!=nil && pre.Val>cur.Val{        if first==nil{            first=pre            second=cur        }else{            second=cur        }    }    pre=cur     midOrder(cur.Right)}

看完上述內(nèi)容是否對(duì)您有幫助呢？如果還想對(duì)相關(guān)知識(shí)有進(jìn)一步的了解或閱讀更多相關(guān)文章，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對(duì)創(chuàng)新互聯(lián)的支持。