当前位置:网站首页>Leetcode brush questions: binary tree 18 (largest binary tree)
Leetcode brush questions: binary tree 18 (largest binary tree)
2022-07-05 20:03:00 【Taotao can't learn English】
654. The largest binary tree
Given an array of integers without repeating elements . A maximum binary tree constructed from this array is defined as follows :
- The root of a binary tree is the largest element in the array .
- The left subtree is the largest binary tree constructed from the left part of the maximum value in the array .
- Right subtree is the largest binary tree constructed by the right part of the maximum value in the array .
Build the largest binary tree from a given array , And output the root node of the tree .
Example :
Tips :
The size of the given array is [1, 1000] Between .
Traverse , Find the maximum value and its position . The array is divided into left and right subtree arrays . Create nodes and add left and right subtrees . The recursive termination condition is that the left and right arrays are empty , That is, the leaf node .
package com.programmercarl.tree;
/** * @ClassName ConstructMaximumBinaryTree * @Descriotion TODO * @Author nitaotao * @Date 2022/7/5 15:45 * @Version 1.0 * 654. The largest binary tree * 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;
}
}
// Find the current maximum
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});
}
}
边栏推荐
- .Net分布式事务及落地解决方案
- leetcode刷题:二叉树14(左叶子之和)
- ACM getting started Day1
- Leetcode brush question: binary tree 14 (sum of left leaves)
- 618 "low key" curtain call, how can baiqiushangmei join hands with the brand to cross the "uncertain era"?
- 2023年深圳市绿色低碳产业扶持计划申报指南
- . Net distributed transaction and landing solution
- Is it safe to open a mobile stock account? Is it reliable?
- 深度学习 卷积神经网络(CNN)基础
- Postman core function analysis - parameterization and test report
猜你喜欢
Autumn byte interviewer asked you any questions? In fact, you have stepped on thunder
Leetcode brush question: binary tree 14 (sum of left leaves)
Go language | 03 array, pointer, slice usage
图嵌入Graph embedding学习笔记
四万字长文说operator new & operator delete
CADD课程学习(7)-- 模拟靶点和小分子相互作用 (半柔性对接 AutoDock)
城链科技数字化创新战略峰会圆满召开
Interviewer: what is the internal implementation of set data types in redis?
Base du réseau neuronal de convolution d'apprentissage profond (CNN)
ACM getting started Day1
随机推荐
[FAQ] summary of common causes and solutions of Huawei account service error 907135701
[C language] three implementations of quick sorting and optimization details
国信证券在网上开户安全吗?
Thread pool parameters and reasonable settings
C - sequential structure
【obs】libobs-winrt :CreateDispatcherQueueController
Parler de threadlocal insecurerandom
Leetcode brush questions: binary tree 11 (balanced binary tree)
Build your own website (16)
安信证券在网上开户安全吗?
ICTCLAS用的字Lucene4.9捆绑
sun.misc.BASE64Encoder报错解决方法[通俗易懂]
C language OJ gets PE, OJ of ACM introduction~
Do you know several assertion methods commonly used by JMeter?
Common operators and operator priority
Float. The specific meaning of the return value of floattorawintbits is to convert float into byte array
Go language | 01 wsl+vscode environment construction pit avoidance Guide
leetcode刷题:二叉树17(从中序与后序遍历序列构造二叉树)
SecureRandom那些事|真伪随机数
常用运算符与运算符优先级