0%

机试——二叉搜索树转双向链表

发表于 更新于 阅读次数： Valine：
本文字数： 106 阅读时长 ≈ 1 分钟

题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向

设计到二叉搜索树基本上绕不过的思路就是中序遍历，这道题的思路依然是在中序遍历的基础上进行的改进

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	def __init__():
		self.listHead = None   #用来标记双向链表的起始节点
    self.listtail = None   #用来标记当前正在调整的节点
  def Convert(pRoot):
    if pRoot==None:
      return 
    
    self.Convert(pRoot.left)
    
    if self.listHead==None:  
      self.listHead = pRoot   #第一个节点时，直接将两个指针指向这两个节点
      self.listTail = pRoot
    else:
      self.listTail.right = pRoot   #核心：后面的节点,pRoot相当于下一个节点 ，可以从栈的角度进行想象
      pRoot.left = self.listTail
      self.listTail = pRoot
    
    self.Convert(pRoot.right)
    
    return self.listHead