forked from UmassJin/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Max_Tree.py
56 lines (40 loc) · 1.34 KB
/
Max_Tree.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
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
this.val = val
this.left, this.right = None, None
"""
# Recursion: TLE, O(n^2)
class Solution:
# @param A: Given an integer array with no duplicates.
# @return: The root of max tree.
def maxTree_1(self, A):
if not A: return None
return self.buildTree(A, 0, len(A)-1)
def buildTree(self, A, start, end):
if start > end:
return None
if start == end:
return TreeNode(A[start])
maxvalue = max(A[start: end+1])
max_index = A.index(maxvalue)
root = TreeNode(maxvalue)
root.left = self.buildTree(A, start, max_index-1)
root.right = self.buildTree(A, max_index+1, end)
return root
def maxTree(self, A):
stack = []
for num in A:
newnode = TreeNode(num)
while stack and (stack[-1].val <= newnode.val):
left_neighbor = stack.pop()
left_neighbor.right = newnode.left
newnode.left = left_neighbor
stack.append(newnode)
pre = None
while stack:
cur = stack.pop()
cur.right = pre
pre = cur
return pre