二叉搜索树与双向链表
2018-04-04 本文已影响0人
GoDeep
题目描述
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def Convert(self, root):
# write code here
if not root: return None
def Convert2(root):
if not root.left and not root.right: return root, root
l1=r1=l2=r2=None
if root.left: l1,r1 = Convert2(root.left)
if root.right: l2,r2 = Convert2(root.right)
root.left = r1
if r1: r1.right = root
root.right = l2
if l2: l2.left = root
if not l1 and not r1: return root, r2
if not l2 and not r2: return l1, root
return (l1, r2)
res = Convert2(root)
return res[0]