26 二叉搜尋樹與雙向連結串列

2022-09-22 05:26:40 字數 1196 閱讀 6525

輸入一棵二叉搜尋樹,將該二叉搜尋樹轉換成一個排序的雙向連結串列。要求不能建立任何新的結點,只能調整樹中結點指標的指向。

思路根節點將left連線到左子樹的最右節點,

將right連線到右子樹的最左節點

需要注意的是,我們要返回的是頭節點,即最左邊的節點,所以遞迴返回的是最左邊的節點

右子樹的最左邊節點和根節點之間可以互相連線,但是左子樹需要找到最右,並且當leftnode為空時,返回的應該是根節點本身

下面看**

1

class

solution:

2def

convert(self, prootoftree):3#

write code here

4if prootoftree ==none:

5return

none

6def

find_right(node):

7while

node.right:

8 node=node.right

9return

node

1011 leftnode =self.convert(prootoftree.left)

12 rightnode =self.convert(prootoftree.right)

1314 retnode =leftnode

15if

leftnode:

16 leftnode =find_right(leftnode)

17else

:18 retnode =prootoftree

1920 prootoftree.left =leftnode

21 prootoftree.right =rightnode

2223

if leftnode !=none :

24 leftnode.right =prootoftree

25if rightnode !=none:

26 rightnode.left =prootoftree

27return

retnode

2019-12-17 16:40:17