题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
python3，典型的中序遍历
中序遍历，两个指针记录前驱结点和后驱结点，递归后驱结点，为空时前驱结点到达尾部（即最大/最右）。如果要求做成循环列表，额外连上首尾即可。
class Solution: def Convert(self , pRootOfTree ): def dfs(cur): if not cur: return dfs(cur.left) # 递归左子树 if self.pre: # 修改节点引用 self.pre.right, cur.left = cur, self.pre else: # 记录头节点 self.head = cur self.pre = cur # 保存 cur dfs(cur.right) # 递归右子树 if not pRootOfTree: return self.pre = None dfs(pRootOfTree) # 如果做成循环链表，只需把首位连上即可。首即head，尾即pre # self.head.left, self.pre.right = self.pre, self.head return self.head
