二叉搜索树与双向链表

题目描述

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

解答

二叉搜索树的特点，左子树的节点值都小于根节点值，右子树的节点值都大于根节点值。

先使用中序遍历方式，将二叉搜索树的节点按值的升序方式放到一个列表内。

然后给列表内的节点设置指针。

# coding:utf-8
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def __init__(self):
        # 创建一个列表
        self.l1 = []

    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        # 升序方式将节点放到self.l1里面
        self.inner(pRootOfTree)
        # 设置right指针
        for i in range(len(self.l1)):
            if i < len(self.l1)-1:
                self.l1[i].right = self.l1[i+1]
        # 创建left指针
        for i in range(len(self.l1)):
            if i > 0:
                self.l1[i].left = self.l1[i-1]
        # 返回第一个节点
        return self.l1[0] if self.l1[0] else None
    # 中序遍历方式
    def inner(self, root):
        if root:
            self.inner(root.left)
            self.l1.append(root)
            self.inner(root.right)

# 创建节点验证
a = TreeNode("1")
b = TreeNode("3")
c = TreeNode("4")
d = TreeNode("5")
e = TreeNode("7")
f = TreeNode("8")
g = TreeNode("9")

# 创建二叉搜索树
d.left = b
b.left = a
b.right = c
d.right = f
f.left = e
f.right = g


p = Solution()
ret = p.Convert(d)

r1 = ret
r2 = ret
probe = None
while r1:
    print r1.val
    r1 = r1.right

while r2:
    r2 = r2.right
    if r2.right == None:
        probe = r2
        break

while probe:
    print probe.val
    probe = probe.left

结束！