-
Notifications
You must be signed in to change notification settings - Fork 0
/
convert_binary_search_treee_doubly_ll.py
90 lines (71 loc) · 2.39 KB
/
convert_binary_search_treee_doubly_ll.py
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# Definition for a Node.
class Node(object):
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution(object):
def treeToDoublyList(self, root):
"""
:type root: Node
:rtype: Node
"""
if root:
head, tail = self.helper(root)
return head
return None
def helper(self, root):
head, tail = root, root
if root.left:
lh, lt = self.helper(root.left)
lt.right = root
root.left = lt
head = lh
if root.right:
rh, rt = self.helper(root.right)
rh.left = root
root.right = rh
tail = rt
head.left = tail
tail.right = head
return(head, tail)
# self.head = None
# self.tail = None
# if not root.left and not root.right:
# root.left = root
# root.right = root
# return root
# def joinNodes(main_root, root, is_right):
# if not root:
# return
# left_node = joinNodes(main_root, root.left, False)
# right_node = joinNodes(main_root, root.right, True)
# if not left_node and not right_node:
# if not is_right:
# self.head = root
# else:
# self.tail = root
# return root
# if left_node:
# left_node.right = root
# root.left = left_node
# if right_node:
# right_node.left = root
# if root == main_root:
# if right_node:
# if self.tail and not self.head:
# self.head = root
# self.tail.right = self.head
# self.head.left = self.tail
# else:
# root.right = self.head
# self.head.left = root
# return self.head
# elif left_node and right_node:
# return right_node
# else:
# return root
# return joinNodes(root, root, False)
node = Node(1, None, Node(2, None, None))
abc = Solution()
print (abc.treeToDoublyList(node))