当前位置:网站首页>leetcode刷题:二叉树18(最大二叉树)
leetcode刷题:二叉树18(最大二叉树)
2022-07-05 19:52:00 【涛涛英语学不进去】
654.最大二叉树
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
- 二叉树的根是数组中的最大元素。
- 左子树是通过数组中最大值左边部分构造出的最大二叉树。
- 右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。
示例 :
提示:
给定的数组的大小在 [1, 1000] 之间。
遍历,找最大值和其位置。数组分割为左右子树数组。创建结点添加左右子树。递归终止条件为左右数组都为空,即为叶子结点。
package com.programmercarl.tree;
/** * @ClassName ConstructMaximumBinaryTree * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 15:45 * @Version 1.0 * 654. 最大二叉树 * https://leetcode.cn/problems/maximum-binary-tree/ **/
public class ConstructMaximumBinaryTree {
public TreeNode constructMaximumBinaryTree(int[] nums) {
if (nums.length == 0) {
return null;
}
int max = -1;
int maxIndex = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > max) {
max = nums[i];
maxIndex = i;
}
}
//找到当前最大值
TreeNode root = new TreeNode(nums[maxIndex]);
// 6 - 3 = 3
int[] leftNums = new int[maxIndex];
// 6 - 3 - 1 = 2
int[] rightNums = new int[nums.length - maxIndex - 1];
for (int i = 0; i < nums.length; i++) {
if (i < maxIndex) {
leftNums[i] = nums[i];
} else if (i > maxIndex) {
rightNums[i - maxIndex - 1] = nums[i];
}
}
// System.out.println(leftNums);
// System.out.println(rightNums);
root.left = constructMaximumBinaryTree(leftNums);
root.right = constructMaximumBinaryTree(rightNums);
return root;
}
public static void main(String[] args) {
new ConstructMaximumBinaryTree().constructMaximumBinaryTree(new int[]{
3,2,1,6,0,5});
}
}
边栏推荐
- Bitcoinwin (BCW)受邀参加Hanoi Traders Fair 2022
- [FAQ] summary of common causes and solutions of Huawei account service error 907135701
- Apprentissage du projet MMO I: préchauffage
- What is the core value of testing?
- 建立自己的网站(16)
- Interviewer: what is the internal implementation of set data types in redis?
- 如何在2022年更明智地应用智能合约?
- 期货如何网上开户?安不安全?
- Jvmrandom cannot set seeds | problem tracing | source code tracing
- redis集群模拟消息队列
猜你喜欢
浅浅的谈一下ThreadLocalInsecureRandom
JMeter 常用的几种断言方法,你会了吗?
全网最全的低代码/无代码平台盘点:简道云、伙伴云、明道云、轻流、速融云、集简云、Treelab、钉钉·宜搭、腾讯云·微搭、智能云·爱速搭、百数云
众昂矿业:2022年全球萤石行业市场供给现状分析
How to safely and quickly migrate from CentOS to openeuler
MMO项目学习一:预热
Zhongang Mining: analysis of the current market supply situation of the global fluorite industry in 2022
Worthy of being a boss, byte Daniel spent eight months on another masterpiece
Explain in detail the functions and underlying implementation logic of the groups sets statement in SQL
What do software test engineers do? How about the prospect of treatment?
随机推荐
Bitcoinwin (BCW) was invited to attend Hanoi traders fair 2022
What is the core value of testing?
Four methods of random number generation | random | math | threadlocalrandom | securityrandom
openh264解码数据流向分析
软件测试工程师是做什么的?待遇前景怎么样?
Summer Challenge database Xueba notes, quick review of exams / interviews~
JMeter 常用的几种断言方法,你会了吗?
如何安全快速地从 Centos迁移到openEuler
多分支结构
MMO项目学习一:预热
Debezium series: modify the source code to support drop foreign key if exists FK
Two pits exported using easyexcel template (map empty data columns are disordered and nested objects are not supported)
95后阿里P7晒出工资单:狠补了这个,真香...
Based on vs2017 and cmake GUI configuration, zxing and opencv are used in win10 x64 environment, and simple detection of data matrix code is realized
大厂面试必备技能,2022Android不死我不倒
建立自己的网站(16)
No matter how busy you are, you can't forget safety
Fundamentals of shell programming (Chapter 9: loop)
Fundamentals of shell programming (Part 8: branch statements -case in)
手机股票开户安全吗?靠不靠谱啊?