劍指 Offer 36. 二叉搜索樹與雙向鏈表

輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的循環(huán)雙向鏈表。要求不能創(chuàng)建任何新的節(jié)點，只能調(diào)整樹中節(jié)點指針的指向。

?

為了讓您更好地理解問題，以下面的二叉搜索樹為例：

我們希望將這個二叉搜索樹轉(zhuǎn)化為雙向循環(huán)鏈表。鏈表中的每個節(jié)點都有一個前驅(qū)和后繼指針。對于雙向循環(huán)鏈表，第一個節(jié)點的前驅(qū)是最后一個節(jié)點，最后一個節(jié)點的后繼是第一個節(jié)點。

下圖展示了上面的二叉搜索樹轉(zhuǎn)化成的鏈表。“head” 表示指向鏈表中有最小元素的節(jié)點。

特別地，我們希望可以就地完成轉(zhuǎn)換操作。當(dāng)轉(zhuǎn)化完成以后，樹中節(jié)點的左指針需要指向前驅(qū)，樹中節(jié)點的右指針需要指向后繼。還需要返回鏈表中的第一個節(jié)點的指針。

?

嗯這道題就是dfs的變型，一開始沒想到，我太菜了

"""

#?Definition?for?a?Node.

class?Node:

????def?__init__(self,?val,?left=None,?right=None):

????????self.val?=?val

????????self.left?=?left

????????self.right?=?right

"""

class?Solution:

????def?treeToDoublyList(self,?root:?'Node')?->?'Node':

????????if?not?root:return

????????self.head=None

????????self.pre=None

????????def?dfs(cur):

????????????if?cur==None:return

????????????dfs(cur.left)

????????????if?self.pre==None:

????????????????self.head=cur

????????????else:

????????????????self.pre.right=cur

????????????cur.left=self.pre

????????????self.pre=cur

????????????dfs(cur.right)

????????dfs(root)

????????self.head.left=self.pre

????????self.pre.right=self.head

????????return?self.head