剑指offer 二叉搜索树与双向链表

Posted on |

二叉搜索树与双向链表

题目

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

方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        res=self.inorder(pRootOfTree)
        if len(res)==0:
            return None
        elif len(res)==1:
            return pRootOfTree

        res[0].left=None
        res[0].right=res[1]
        res[-1].left=res[-2]
        res[-1].right=None

        for i in range(1,len(res)-1):
            res[i].left=res[i-1]
            res[i].right=res[i+1]
        return res[0]
    def inorder(self,node):
        if not node:
            return []
        return self.inorder(node.left)+[node]+self.inorder(node.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree or (not pRootOfTree.left and not pRootOfTree.right):
            return pRootOfTree

        # 处理左子树
        self.Convert(pRootOfTree.left)
        left=pRootOfTree.left
        # 连接根与左子树最大结点
        if left:
            while left.right:
                left=left.right
            pRootOfTree.left,left.right=left,pRootOfTree

        # 处理右子树
        self.Convert(pRootOfTree.right)
        right=pRootOfTree.right
        # 连接根与右子树最小结点
        if right:
            while right.left:
                right=right.left
            pRootOfTree.right,right.left=right,pRootOfTree

        while pRootOfTree.left:
            pRootOfTree=pRootOfTree.left
        return pRootOfTree