leetcode-654 最大二叉树

题目描述:给定一个不含重复元素的整数数组 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) {
//1. 判空
if (start >= end) {
return null;
}

//2. 单个元素直接返回
if (start == end - 1) {
TreeNode node = new TreeNode(nums[start]);
return node;
}

//3. 寻找最大元素
int maxVal = nums[start];
int maxIdx = start;
for (int idx = start; idx < end; idx++) {
if (nums[idx] > maxVal) {
maxVal = nums[idx];
maxIdx = idx;
}
}

//4. 最大元素为根节点
TreeNode root = new TreeNode(maxVal);

//5. 最大元素左边为左子树
TreeNode leftNode = constructMaximumBinaryTree(nums, start, maxIdx);

//6. 最大元素右边为右子树
TreeNode rightNode = constructMaximumBinaryTree(nums, maxIdx + 1, end);

//7. 连接左右子树
root.left = leftNode;
root.right = rightNode;
return root;
}
}