题目地址(654. 最大二叉树)

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

题目描述

  1. 给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
  3. 二叉树的根是数组 nums 中的最大元素。
  4. 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
  5. 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
  7. 返回有给定数组 nums 构建的 最大二叉树 。
  11. 示例 1：
  13. 输入：nums = [3,2,1,6,0,5]
  14. 输出：[6,3,5,null,2,0,null,null,1]
  15. 解释：递归调用如下所示：
  16. - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
  17.     - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
  18.         - 空数组，无子节点。
  19.         - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
  20.             - 空数组，无子节点。
  21.             - 只有一个元素，所以子节点是一个值为 1 的节点。
  22.     - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
  23.         - 只有一个元素，所以子节点是一个值为 0 的节点。
  24.         - 空数组，无子节点。
  27. 示例 2：
  29. 输入：nums = [3,2,1]
  30. 输出：[3,null,2,null,1]
  35. 提示：
  37. 1 <= nums.length <= 1000
  38. 0 <= nums[i] <= 1000
  39. nums 中的所有整数 互不相同

前置知识


公司

  • 暂无

思路

关键点


代码

  • 语言支持：Java

Java Code:

  2. /**
  3.  * Definition for a binary tree node.
  4.  * public class TreeNode {
  5.  *     int val;
  6.  *     TreeNode left;
  7.  *     TreeNode right;
  8.  *     TreeNode() {}
  9.  *     TreeNode(int val) { this.val = val; }
  10.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  11.  *         this.val = val;
  12.  *         this.left = left;
  13.  *         this.right = right;
  14.  *     }
  15.  * }
  16.  */
  17. class Solution {
  18.         public TreeNode constructMaximumBinaryTree(int[] nums) {
  19.             return loop(nums, 0, nums.length-1);
  20.         }
  22.         public TreeNode loop(int[] nums , int left , int right) {
  23.             if (left > right) {
  24.                 return null;
  25.             }
  26.             //找到最大值 和最大值的位置
  27.             int max = Integer.MIN_VALUE;
  28.             int index = 0;
  29.             for (int i = left; i <= right; i++) {
  30.                 if (nums[i] > max) {
  31.                     max = nums[i];
  32.                     index = i;
  33.                 }
  34.             }
  35.             //定义root节点
  36.             TreeNode root = new TreeNode(max);
  37.             //切割
  38.             root.left = loop(nums, left, index - 1);
  39.             root.right = loop(nums, index + 1, right);
  40.             return root;
  41.         }
  42.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：654. 最大二叉树 - 图1#card=math&code=O%28n%29&id=EFkBK)
  • 空间复杂度：654. 最大二叉树 - 图2#card=math&code=O%28n%29&id=OxHPZ)