You are given an integer array nums
with no duplicates. A maximum binary tree can be built recursively from nums
using the following algorithm:
- Create a root node whose value is the maximum value in
nums
. - Recursively build the left subtree on the subarray prefix to the left of the maximum value.
- Recursively build the right subtree on the subarray suffix to the right of the maximum value.
Return the maximum binary tree built from nums
.
Example 1:
Input: nums = [3,2,1,6,0,5] Output: [6,3,5,null,2,0,null,null,1] Explanation: The recursive calls are as follow: - The largest value in [3,2,1,6,0,5] is 6. Left prefix is [3,2,1] and right suffix is [0,5]. - The largest value in [3,2,1] is 3. Left prefix is [] and right suffix is [2,1]. - Empty array, so no child. - The largest value in [2,1] is 2. Left prefix is [] and right suffix is [1]. - Empty array, so no child. - Only one element, so child is a node with value 1. - The largest value in [0,5] is 5. Left prefix is [0] and right suffix is []. - Only one element, so child is a node with value 0. - Empty array, so no child.
Example 2:
Input: nums = [3,2,1] Output: [3,null,2,null,1]
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
- All integers in
nums
are unique.
最大二叉树。
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题的题目描述,就是在暗示其实是可以用递归的思路做的。我们用一个函数找到数组中的最大值及其index,然后用分治的思路递归去构建左子树和右子树。
时间O(nlogn) - average; O(n^2) - worst case
空间O(n)
Java实现
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class Solution { 17 public TreeNode constructMaximumBinaryTree(int[] nums) { 18 return helper(nums, 0, nums.length); 19 } 20 21 private TreeNode helper(int[] nums, int left, int right) { 22 if (left == right) { 23 return null; 24 } 25 int maxIndex = max(nums, left, right); 26 TreeNode root = new TreeNode(nums[maxIndex]); 27 root.left = helper(nums, left, maxIndex); 28 root.right = helper(nums, maxIndex + 1, right); 29 return root; 30 } 31 32 private int max(int[] nums, int left, int right) { 33 int maxIndex = left; 34 for (int i = left; i < right; i++) { 35 if (nums[maxIndex] < nums[i]) { 36 maxIndex = i; 37 } 38 } 39 return maxIndex; 40 } 41 }
这道题还有一个类似单调栈的做法但是很不好想,我把引用贴在这里,有兴趣可以看一下,运行速度其实并没有非常快。