题目描述:给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下:
- 二叉树的根是数组 nums 中的最大元素。
- 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
- 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
代码实现
递归实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| class Solution { public TreeNode constructMaximumBinaryTree(int[] nums) { return constructMaximumBinaryTree(nums, 0, nums.length); }
public TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) { if (start >= end) { return null; }
if (start == end - 1) { TreeNode node = new TreeNode(nums[start]); return node; }
int maxVal = nums[start]; int maxIdx = start; for (int idx = start; idx < end; idx++) { if (nums[idx] > maxVal) { maxVal = nums[idx]; maxIdx = idx; } }
TreeNode root = new TreeNode(maxVal);
TreeNode leftNode = constructMaximumBinaryTree(nums, start, maxIdx);
TreeNode rightNode = constructMaximumBinaryTree(nums, maxIdx + 1, end);
root.left = leftNode; root.right = rightNode; return root; } }
|