题目描述：

LeetCode 654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example 1:

Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

Note:

1. The size of the given array will be in the range [1,1000].

题目大意：

给定无重复的数组。一棵最大树定义如下：

从数组中挑选最大的数字作为根

挑选左半数组中最大的数字作为左子树的根

挑选右半数组中最大的数字作为右子树的根

递归此过程。

解题思路：

按照题目描述中的过程模拟即可

Python代码：

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if not nums: return None
        maxn = max(nums)
        idx = nums.index(maxn)
        node = TreeNode(maxn)
        node.left = self.constructMaximumBinaryTree(nums[:idx])
        node.right = self.constructMaximumBinaryTree(nums[idx+1:])
        return node

 

本文链接：http://bookshadow.com/weblog/2017/08/06/leetcode-maximum-binary-tree/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码