題目
輸入一棵二叉搜索樹，將該二叉搜索樹轉換成一個排序的循環(huán)雙向鏈表疫粥。要求不能創(chuàng)建任何新的節(jié)點茬斧，只能調整樹中節(jié)點指針的指向。
為了讓您更好地理解問題梗逮，以下面的二叉搜索樹為例：
我們希望將這個二叉搜索樹轉化為雙向循環(huán)鏈表项秉。鏈表中的每個節(jié)點都有一個前驅和后繼指針。對于雙向循環(huán)鏈表慷彤，第一個節(jié)點的前驅是最后一個節(jié)點娄蔼，最后一個節(jié)點的后繼是第一個節(jié)點。
下圖展示了上面的二叉搜索樹轉化成的鏈表底哗∷晁撸“head” 表示指向鏈表中有最小元素的節(jié)點。
特別地跋选，我們希望可以就地完成轉換操作涕癣。當轉化完成以后，樹中節(jié)點的左指針需要指向前驅野建，樹中節(jié)點的右指針需要指向后繼属划。還需要返回鏈表中的第一個節(jié)點的指針恬叹。
注意：本題與主站 426 題相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
注意：此題對比原題有改動。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作權歸領扣網絡所有同眯。商業(yè)轉載請聯(lián)系官方授權绽昼，非商業(yè)轉載請注明出處。
解法
首先是遞歸须蜗，前序遍歷硅确。
但是問題是，在最后的結果中明肮，root左邊的不是root.left菱农，這就需要把左子樹和root相接的節(jié)點找出來，同理柿估，右子樹也要找出來循未。
我的解法
由于左右子樹的處理方式不一樣，所以只傳root進行遞歸不夠用秫舌，就加上了標記位isLeft的妖，如果處理的節(jié)點是左節(jié)點，連接好之后足陨，一直向右找到尾巴返回嫂粟。
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root: return None
last = self.convert(root, True)
while root.left : root = root.left
root.left = last
last.right = root
return root
def convert(self, root, isLeft):
if not root : return None
if root.left:
root.left = self.convert(root.left, isLeft)
root.left.right = root
if root.right:
root.right = self.convert(root.right, not isLeft)
root.right.left = root
pLastNode = root
if isLeft:
while pLastNode.right : pLastNode = pLastNode.right
else:
while pLastNode.left : pLastNode = pLastNode.left
return pLastNode
大佬解法
劍指面試題[36]——二叉搜索樹與雙向鏈表 - 挪羅兒的文章 - 知乎
https://zhuanlan.zhihu.com/p/105103682
我全都要，返回的時候直接把左右兩邊都返回墨缘，就不需要像我這樣每次跑這么遠去找頭或者尾巴星虹。
class Solution:
def treeToDoublyList(self, root: 'Node') -> 'Node':
if not root: return None
l_head, r_tail = self.convert(root)
l_head.left, r_tail.right = r_tail,l_head
return l_head
def convert(self, root):
if root.left:
l_head,l_tail = self.convert(root.left)
l_tail.right = root
root.left = l_tail
else:
l_head = root
if root.right:
r_head, r_tail = self.convert(root.right)
r_head.left = root
root.right = r_head
else:
r_tail = root
return l_head, r_tail
總結
題目本身不難，花了太多時間镊讼。
一開始沒有考慮左右子樹不一樣的問題宽涌，導致每次返回都是一樣的，出錯蝶棋。
后來考慮到护糖，傳參判斷是左子樹還是右子樹。
比較簡單的寫法是左右兩個都返回嚼松。
