原題
給出一個(gè)沒有重復(fù)的整數(shù)數(shù)組瞒爬，在此數(shù)組上建立最大樹的定義如下：
1.根是數(shù)組中最大的數(shù)
2.左子樹和右子樹元素分別是被父節(jié)點(diǎn)元素切分開的子數(shù)組中的最大值
利用給定的數(shù)組構(gòu)造最大樹阎姥。
給出數(shù)組 [2, 5, 6, 0, 3, 1]彼棍，構(gòu)造的最大樹如下：
6
/ \
5 3
/ / \
2 0 1
解題思路
- 通過觀察發(fā)現(xiàn)規(guī)律瞪浸，對(duì)于每個(gè)node的父親節(jié)點(diǎn) = min(左邊第一個(gè)比它大的，右邊第一個(gè)比它大的)
- 維護(hù)一個(gè)降序數(shù)組，可以實(shí)現(xiàn)對(duì)這個(gè)min的快速查找
# stack = [2], push 5 因?yàn)?5 > 2, 所以2是5的左兒子, pop 2
# stack = [], push 5
# stack = [5], push 6, 因?yàn)?6 > 5，所以5是6的左兒子, pop 5
# stack = [], push 6
# stack = [6], push 0, 因?yàn)? < 6, stack = [6], 所以0是6的右兒子
# stack = [6, 0], push 3, 因?yàn)? > 0, 所以0是3的左兒子驼鞭， pop 0
# stack = [6], 所以3是6的右兒子庶弃， push 3
# stack = [6, 3], push 1, 因?yàn)? < 3衫贬，所以1是3的右兒子
完整代碼
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
# @param A: Given an integer array with no duplicates.
# @return: The root of max tree.
def maxTree(self, A):
# write your code here
stack = []
for element in A:
node = TreeNode(element)
while len(stack) != 0 and element > stack[-1].val:
node.left = stack.pop()
if len(stack) != 0:
stack[-1].right = node
stack.append(node)
return stack[0]
