654_最大二叉树

类型：树

• 654. 最大二叉树 💛

  https://leetcode-cn.com/problems/maximum-binary-tree/

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

  • 二叉树的根是数组 nums 中的最大元素。
  • 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
  • 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。

  返回有给定数组 nums 构建的 最大二叉树 。

  💡 递归

  class Solution:
      def geneNode(self, node, arr):
          val = max(arr)
          index = arr.index(val)
          node.val = val
          leftArr = arr[:index]
          rightArr = arr[index + 1:]
          if not leftArr:
              node.left = None
          else:
              node.left = TreeNode()
              self.geneNode(node.left, leftArr)
          if not rightArr:
              node.right = None
          else:
              node.right = TreeNode()
              self.geneNode(node.right, rightArr)
  
      def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
          if not nums:
              return None
          head = TreeNode()
          self.geneNode(head, nums)
          return head

  时间复杂度：O(n^2)，空间复杂度：O(n)