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

Posted on | In |

题目描述

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

如下代码构建了一个二叉搜索树，用于测试用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

L = {'A': TreeNode(3), 
     'B': TreeNode(2), 
     'C': TreeNode(6), 
     'D': TreeNode(1), 
     'E': TreeNode(4), 
     'F': TreeNode(8), 
     'G': TreeNode(5), 
     'H': TreeNode(7), 
     'I': TreeNode(9)}

L['F'].left, L['F'].right = L['H'], L['I']
L['E'].right = L['G']
L['C'].left, L['C'].right = L['E'], L['F']
L['A'].left, L['A'].right = L['B'], L['C']
L['B'].left = L['D']
root = L['A']

递归。

  • 函数recur(root)能够把root为根的树编程一个排序的双向链表，root不变。
  • 已有root，根据双向链表的特性，可以很容易得到该双向链表的收尾节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    # 只要中序遍历即可
    def Convert(self, root):
        def recur(root):
            if root.left:
                recur(root.left)
                lr = root.left
                while lr.right:
                    lr = lr.right
                root.left, lr.right = lr, root
            if root.right:
                recur(root.right)
                rl = root.right
                while rl.left:
                    rl = rl.left
                root.right, rl.left = rl,root
        if root is None:
            return root
        else:
            recur(root)
            while root.left:
                root = root.left
            return root

中序遍历，把节点都存放到一个列表里，然后构建相邻节点之间的双向连接。

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
34
35
36
37
38
39
40
41
42
class Solution:
    # 只要中序遍历即可
    def Convert(self, pRootOfTree):
        # write code here
        # write code here
        logs = set()
        mystack = []
        mylist = []
        node = pRootOfTree
        while node is not None:
            if id(node) not in logs:
                logs.add(id(node))
                mystack.append(node)
                if node.left:
                    node = node.left
                else:
                    node = mystack.pop(-1)
            else:
                mylist.append(node)
                if node.right:
                    node = node.right
                else:
                    # 列表如果不包含元素，则不能用pop否则会出错
                    if len(mystack) > 0:
                        node = mystack.pop(-1)
                    else:
                        node = None
        if len(mylist) == 0:
            return None
        elif len(mylist) == 1:
            mylist[0].left, mylist[0].right = None, None
            return mylist[0]
        else:
            mylist[0].left = None
            mylist[0].right = mylist[1]
            mylist[-1].right = None
            mylist[-1].left = mylist[-2]
            for i in range(1, len(mylist)-1):
                mylist[i].left = mylist[i-1]
                mylist[i].right = mylist[i+1]
            return mylist[0]