面试题36：二叉搜索树与双向链表

题目描述

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

知识点

二叉搜索树，前序遍历

Qiang的思路

从二叉搜索树得到排序的序列可以通过中序遍历实现。

因为要将排完序之后将结果转为双向链表，所以我们排序的节点序列存储到list中。然后将其左指针修改为前向指针，右指针修改为后向指针，这样就得到了排序的双向链表。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def getList(self, root, l):
        if root.left!=None:
            self.getList(root.left, l)
        l.append(root)
        if root.right!=None:
            self.getList(root.right, l)
        
    def Convert(self, pRootOfTree):
        # write code here
        if pRootOfTree==None:
            return None
        l=[]
        self.getList(pRootOfTree, l)
        if len(l)==1:
            return l[0]
        for i in range(1, len(l)-1):
            l[i].right=l[i+1]
            l[i].left=l[i-1]
        l[0].right=l[1]
        l[0].left=None
        l[-1].left=l[-2]
        l[-1].right=None
        return l[0]

Book上的思路

书上是直接在遍历的同时完成了双向链表的构建构成。

可以想到，当左子树和右子树分别构建成为双向链表之后，可以将根节点的左指针指向左子树的最后一个节点，然后左子树最后一个节点的右指针指向根节点，同时，根节点的右指针指向右子树的第一个节点，右子树的第一个节点的左指针指向根节点。这样一步步递归下去便实现了双向链表的构建过程。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def getResult(self, root):
        _l=root
        _r=root
        if root.left!=None:
            l,r=self.getResult(root.left)
            r.right=root
            root.left=r
            _l=l
        if root.right!=None:
            l,r=self.getResult(root.right)
            l.left=root
            root.right=l
            _r=r
        return _l,_r
        
    def Convert(self, pRootOfTree):
        # write code here
        if pRootOfTree==None:
            return None
        l,r=self.getResult(pRootOfTree)
        return l

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。