最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
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
| class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def constructMaximumBinaryTree(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
max_num = nums[0]
head = TreeNode(max_num)
for i in range(1, len(nums)):
node = TreeNode(nums[i])
if node.val > head.val:
node.left = head
head = node
else:
self.add_child_node(head, node)
return head
def add_child_node(self, top, node):
right = top.right
if top.right is None or top.right.val < node.val:
top.right = node
node.left = right
else:
self.add_child_node(right, node)
|
分析原理：
数组从左开始遍历，从head树开始判断
如果数组大于head树，表示当前为最大值，那么设置head为当前值，且当前值的左边为原树，因为左子树是通过数组中最大值左边部分构造出的最大二叉树。
如果小于head树，递归调用head 右树，如果大于该节点，那么原节点下降，当前节点补上该节点，原下降节点设置为当前节点左树左子树是通过数组中最大值左边部分构造出的最大二叉树。。如果小于该节点，那么一直从右节点向下查找，直到满足条件。