LeetCode 654 Maximum Binary Tree

题意

给定一个整数数组,生成一棵 最大二叉树,规则是数组中的最大值为根节点,然后分割出最大值左侧的子数组再构造 最大二叉树,最大值的右侧也构造成 最大二叉树

例 :

1
2
3
4
5
6
7
8
9
10
输入: [3,2,1,6,0,5]
输出: 返回表示以下树的根节点:

6
/ \
3 5
\ /
2 0
\
1

解法

根据题意,是经典的分而治之的题目,用递归就可以很简单的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public TreeNode constructMaximumBinaryTree(int[] nums) {
int len = nums.length;
if (len == 0) {
return null;
}

int max = Integer.MIN_VALUE;
int maxIndex = -1;
for (int i = 0; i < len; i++) {
int num = nums[i];
if (num > max) {
max = num;
maxIndex = i;
}
}
TreeNode node = new TreeNode(max);
node.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxIndex));
node.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxIndex + 1, len));
return node;
}

Runtime: 6 ms, faster than 69.99% of Java online submissions for Maximum Binary Tree.

Memory Usage: 39.1 MB, less than 88.96% of Java online submissions for Maximum Binary Tree.

  • 本文作者: 赵俊
  • 本文链接: http://www.zhaojun.im/leetcode-654/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!