题目描述
分析
class Stack(object): def __init__(self): self.item = [] def isEmpty(self): return self.item == [] def push(self,newElem): self.item.append(newElem) def pop(self): if self.isEmpty(): raise Exception("Your stack is empty!") else: return self.item.pop() def peek(self): if self.isEmpty(): raise Exception("Your stack is Empty!") else: return self.item[len(self.item)-1] def size(self): return len(self.item) class TreeNode(object): def __init__(self,data): self.value = data self.left = None self.right = None def popStackSetMap(stack,map): popNode = stack.pop() if stack.isEmpty(): map[popNode] = None else: map[popNode] = stack.peek() def getMaxTree(arr): nArr = [] for i in arr: nArr.append(TreeNode(i)) stack = Stack() lBigMap = {} rBigMap = {} for i in nArr: curNode = i while stack.isEmpty() != True and stack.peek().value < curNode.value: popStackSetMap(stack,lBigMap) stack.push(curNode) while stack.isEmpty() != True: popStackSetMap(stack,lBigMap) for i in reversed(nArr): curNode = i while stack.isEmpty() != True and stack.peek().value < curNode.value: popStackSetMap(stack,rBigMap) stack.push(curNode) while stack.isEmpty() != True: popStackSetMap(stack,rBigMap) head =None for i in nArr: curNode = i left = lBigMap[i] right = rBigMap[i] if left == None and right == None: head = curNode elif left == None: if right.left == None: right.left = curNode else: right.right = curNode elif right == None: if left.left == None: left.left = curNode else: left.right = curNode else: if left.value < right.value: parent = left else: parent = right if parent.left == None: parent.left = curNode else: parent.right = curNode return head if __name__ == "__main__": arr = [3,4,5,1,2] print(getMaxTree(arr).value)