426. 将二叉搜索树转化为排序的双向链表
Difficulty
Medium
Tags
链表
二叉树
Star
1. 题目
将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。
对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
特别地，我们希望可以 就地 完成转换操作。 当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。 还需要返回链表中最小元素的指针。
示例 1：
示例 2： 输入：root = [2,1,3] 输出：[1,2,3] 示例 3： 输入：root = [] 输出：[] 解释：输入是空树，所以输出也是空链表。 示例 4： 输入：root = [1] 输出：[1] 提示： -1000 <= Node.val <= 1000 Node.left.val < Node.val < Node.right.val Node.val 的所有值都是独一无二的 0 <= Number of Nodes <= 2000
法 1 中序遍历 迭代写法
采用二叉树的非递归遍历写法即可
""" # 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: 'Optional[Node]') -> 'Optional[Node]': if root is None: return None dummy = Node(0) prev = dummy res = dummy stack = [] cur = root while cur or stack: if cur: stack.append(cur) cur = cur.left else: cur = stack.pop() prev.right = cur cur.left = prev prev = cur cur = cur.right prev.right = res.right res.right.left = prev return res.right
法 2 递归
思路
采用递归的模板
