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

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

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

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

示例 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，二叉樹(shù)的性質(zhì)：左子樹(shù)<根<小于右子樹(shù)

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

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

4，如何得到遞增序列？

   中序遍歷

5，用pre記錄中序遍歷的上一個(gè)位置，如果pre.val>cur.val說(shuō)明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)的支持。

本文題目：golang中怎么利用leetcode恢復(fù)二叉搜索樹(shù)
鏈接URL：http://vcdvsql.cn/article2/gjopic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、全網(wǎng)營(yíng)銷推廣、移動(dòng)網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計(jì)、微信公眾號(hào)、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)