原文发表于个人博客:剑指offer 36:二叉搜索树与双向链表
问题描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点,只能调整树中结点指针的指向。
注意:
- 需要返回双向链表最左侧的节点。
例如,输入下图中左边的二叉搜索树,则输出右边的排序双向链表。
问题分析
我们知道二叉搜索树满足以下性质:
- 根节点的值大于左孩子节点,小于右孩子节点;
- 中序遍历得到的值数组是有序数组
而我们最终需要的恰好是排序好的双向链表,且双向链表和二叉树搜索相似,每个节点都存在两个指针。因此,最直观的方法是采用中序遍历的思想来解决该问题。
方案一:中序遍历
可以发现,在将二叉搜索树转化为双向链表的过程中,实际上就是在中序遍历时,将当前节点的左指针指向前一个节点,同时前一个节点的右指针指向当前节点。
由于需要在遍历的过程中进行指针的变换,我们这里采用非递归的中序遍历来解决该问题。
from collections import deque
def convert(root):
if (not root) or (not root.left and not root.right):
return root
# 采用中序遍历的思想
prev = TreeNode(0)
head = prev # 增加一个哨兵节点
stack = deque()
while root or stack:
if root:
stack.append(root)
root = root.left # 遍历左孩子节点
else:
root = stack.pop()
cur = root
cur.left = prev # 当前节点的左指针指向前一个节点
prev.right = cur # 前一个节点的右指针指向当前节点
prev = cur # 当前节点变为前一个节点
root = root.right # 处理右孩子节点
ans = head.right
ans.left = None
return ans
方案二:递归
我们可以将二叉搜索树转化为双向链表的过程看出三部分:根节点、左子树和右子树
则双向链表的构建实质上就是将左子树的最大节点与根节点相连,右子树的最小节点与根节点相连,然后递归处理左右子树。
针对每棵子树,我们需要该子树的最左侧的节点,以及最右侧的节点,因此递归函数 dfs(root)
返回的就应该是以 root
为根节点的子树的最小节点和最大节点 pair(lside, rside)
。
def convert(root):
if not root:
return None
sides = dfs(root)
return sides[0]
def dfs(root):
if not root.left and not root.right: # 无子节点
return [root, root]
if root.left and root.right:
lside = dfs(root.left) # 递归左子树,最右侧节点与根节点相连
lside[1].right = root
root.left = lside[1]
rside = dfs(root.right) # 递归右子树,最左侧节点与根节点相连
rside[0].left = root
root.right = rside[0]
return [lside[0], rside[1]] # 最终返回最小和最大的节点
# 只有左子树或者只有右子树的情况,最终同样范围最小和最大的节点
if root.left:
lside = dfs(root.left)
lside[1].right = root
root.left = lside[1]
return [lside[0], root]
if root.right:
rside = dfs(root.right)
rside[0].left = root
root.right = rside[0]
return [root, rside[1]]