溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶(hù)服務(wù)條款》

golang中怎么利用leetcode 恢復(fù)二叉搜索樹(shù)

發(fā)布時(shí)間：2021-07-06 15:15:38 來(lái)源：億速云 閱讀：201 作者：Leah 欄目：大數(shù)據(jù)

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

二叉搜索樹(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)注億速云行業(yè)資訊頻道，感謝您對(duì)億速云的支持。

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手