题解 | #二叉搜索树与双向链表#

二叉搜索树与双向链表

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)