题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
解题思路
实际上，只需要将搜索二叉树的结点从小到大排列起来，然后再遍历一遍修改左右节点的指向。而搜索二叉树的结点从小到大的排列即为中序遍历的结果。
代码
Python(2.7.3)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# -*- 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 pRootOfTree is None:
return
in_order_nodes = self.in_order(pRootOfTree, [])
for i in range(len(in_order_nodes)):
if i == len(in_order_nodes) - 1:
break
in_order_nodes[i].right = in_order_nodes[i + 1]
in_order_nodes[i + 1].left = in_order_nodes[i]
return in_order_nodes[0]
def in_order(self, pRoot, res):
if pRoot is None:
return
self.in_order(pRoot.left, res)
res.append(pRoot)
self.in_order(pRoot.right, res)
return res运行时间：25ms占用内存：5728k