leetcode-654 最大二叉树

  • English:

654. 最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:

二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。 右子树是通过数组中最大值右边部分构造出的最大二叉树。 通过给定的数组构建最大二叉树,并且输出这个树的根节点。

示例 :

1
2
3
4
5
6
7
8
9
10
输入:[3,2,1,6,0,5]
输出:返回下面这棵树的根节点:

6
/ \
3 5
\ /
2 0
\
1

思路是先找到数组中最大的值,然后左右部分循环递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
if len(nums)<= 0:
return
max_num = max(nums)
root = TreeNode(max_num)
left_nums = nums[:nums.index(max_num)]
right_nums = nums[nums.index(max_num)+1:]
left = self.constructMaximumBinaryTree(left_nums)
right = self.constructMaximumBinaryTree(right_nums)
root.left = left
root.right = right
return root
-------The end of this article  Thank you for your reading-------
  • 本文作者: Eree
  • 本文链接: https://ereebay.me/posts/5767/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!