题解 | #二叉搜索树与双向链表#
二叉搜索树与双向链表
http://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
【剑指offer】二叉搜索树与双向链表（python）
思路：将所有结点中序遍历到一个列表，因为是左中右遍历，因为二叉搜索树自身的性质，所以遍历后就是升序的有序数组，这是再让每个结点（最后一个结点不用设置）的right设为下一个结点，left设为上一个结点。
1. python 的enumerate() 函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。返回 enumerate(枚举) 对象。
enumerate(sequence, [start=0])
2. a[:-1] 除了最后一个取全部。a[2::-1]) 取从下标为2的元素翻转读取。在“从头到尾打印链表”里，也有list切片操作。list[begin_idx: end_idx: step]对列表进行切片操作。从索引 begin_idx 开始，如果 step 为正则向右按 step 的值为步进切片至 end_idx 的前一个元素结束； 如果 step 为负则向左按 step 的值为步进切片至 end_idx 的前一个元素结束。arr[::-1]就是从头到尾按step=-1遍历，也就是从尾到头。
3. 别忘了self.arr清空
4. arr列表中的元素是链表节点，而且列表第一个元素就是双向链表头节点，所以直接返回 self.arr[0] 就相等于直接返回整个双向链表了。
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: arr = [] def Convert(self, pRootOfTree): # write code here if not pRootOfTree: return self.arr = [] self.midTraversal(pRootOfTree) for index,node in enumerate(self.arr[:-1]): node.right = self.arr[index+1] self.arr[index+1].left = node return self.arr[0] def midTraversal(self,root): if not root: return self.midTraversal(root.left) self.arr.append(root) self.midTraversal(root.right)
直接遍历时修改指针：
# -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def Convert(self, pRootOfTree): if not pRootOfTree: return self.head = self.pre = None self.MidTraversal(pRootOfTree) return self.head def MidTraversal(self, root): if not root: return self.MidTraversal(root.left) if not self.head: self.head = self.pre = root else: self.pre.right, root.left, self.pre = root, self.pre, root self.MidTraversal(root.right)
小米集团公司福利 868人发布
