-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy patharrayToTree.py
More file actions
136 lines (120 loc) · 3.21 KB
/
Copy patharrayToTree.py
File metadata and controls
136 lines (120 loc) · 3.21 KB
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#!/usr/bin/env python
#-*- coding: utf-8 -*-
import os,re,sys,commands,glob,math,collections
reload(sys)
sys.setdefaultencoding("utf-8")
# Definition for a binary tree node
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
# list should be reversed
def buildTreeStructure(num):
if not num:
return None
root = TreeNode(0)
num = num - 1
queue = collections.deque([root])
q = collections.deque([])
while len(queue) > 0 and num:
q.clear()
for node in queue:
if num:
node.left = TreeNode(0)
num = num - 1
q.append(node.left)
if num:
node.right = TreeNode(0)
num = num - 1
q.append(node.right)
# swap t queue
t = queue
queue = q
q = t
return root
def middleOrderIn(root, iterable):
if not root:
return
if root.left:
middleOrderIn(root.left, iterable)
root.val = iterable.next()
if root.right:
middleOrderIn(root.right, iterable)
def buildTree(list):
root = buildTreeStructure(len(list))
middleOrderIn(root, iter(list))
return root
class Solution:
def sortedArrayToBST(self, list):
return buildTree((list))
def middleOrderOut(root, results):
if not root:
return results
if root.left:
middleOrderOut(root.left, results)
results.append(root.val)
if root.right:
middleOrderOut(root.right, results)
return results
# def buildTreeLevel(root, level):
# if not root:
# return
# root.level = level
# buildTreeLevel(root.left, level+1)
# buildTreeLevel(root.right, level+1)
def listToNodes(l):
if not l:
return None
head = node = ListNode(0)
for x in l:
n = ListNode(x)
node.next = n
node = n
return head.next
def nodesToList(node):
l = []
while node:
l.append(node.val)
node = node.next
return l
def assertTreeOk(root, level, maxDepth):
if root:
assert level <= maxDepth
if level < maxDepth:
assert root
if not root:
return
if level >= maxDepth:
return
assertTreeOk(root.left, level+1, maxDepth)
assertTreeOk(root.right, level+1, maxDepth)
def doTest(l):
tree = Solution().sortedArrayToBST(l)
assert middleOrderOut(tree, results=[]) == l
# buildTreeLevel(tree, 1)
maxDepth = int(math.ceil(math.log(len(l)+1, 2)))
assertTreeOk(tree, 1, maxDepth);
def test():
doTest(list("4251637"))
doTest(list(""))
doTest(list("0"))
doTest(list("1"))
doTest(list("12"))
doTest(list("123"))
doTest(list("4251637fadsfasdf"))
doTest(list("4251637fadsfasdf1413241321432"))
doTest(list("4251637fadsfasdf1413241321432fdfadsfasdfsdfa"))
doTest(list("4251637fadsfasdf1413241321432fadsfqerw314132fadsfsdfqwr13"))
doTest(list("31432vdvr13fsdfqewr13r1r131434123"))
doTest(list("12312"))
doTest([-1,0,1,2])
def main(args):
pass
if __name__ == '__main__':
main(sys.argv[1:])