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

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

二叉搜索樹中的兩個節(jié)點被錯誤地交換。

請在不改變其結(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

進階:

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

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

解題思路：

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

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

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

4，如何得到遞增序列？

   中序遍歷

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

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)容是否對您有幫助呢？如果還想對相關(guān)知識有進一步的了解或閱讀更多相關(guān)文章，請關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝您對創(chuàng)新互聯(lián)的支持。

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

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

廣告

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