資訊專欄INFORMATION COLUMN
Problem
Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
The root is the maximum number in the array.
The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.
Construct the maximum tree by the given array and output the root node of this tree.
Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:
6
/
3 5
/
2 0
1
Note
The size of the given array will be in the range [1,1000].
Solutionclass Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return constructSubMaxTree(nums, 0, nums.length-1);
}
public TreeNode constructSubMaxTree(int[] nums, int start, int end) {
if (nums == null || nums.length == 0 || start > end) return null;
int maxIndex = findMaxIndex(nums, start, end);
TreeNode root = new TreeNode(nums[maxIndex]);
root.left = constructSubMaxTree(nums, start, maxIndex-1);
root.right = constructSubMaxTree(nums, maxIndex+1, end);
return root;
}
public int findMaxIndex(int[] nums, int start, int end) {
int max = Integer.MIN_VALUE, maxIndex = 0;
for (int i = start; i <= end; i++) {
if (nums[i] > max) {
max = nums[i];
maxIndex = i;
}
}
return maxIndex;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/69363.html
LeetCode 104 Maximum Depth of Binary Tree難度：Easy 題目描述：找到一顆二叉樹(shù)的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...
摘要：但是本題的難點(diǎn)在于，使用遞歸實(shí)現(xiàn)，但是前面的第四種情況不能作為遞歸函數(shù)的返回值，所以我們需要定義兩個(gè)值，代表單邊路徑的最大值，用于遞歸用于和回路的較大值。 Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. For this problem, a path is defined as a...
摘要：復(fù)雜度思路對(duì)于每一節(jié)點(diǎn)，考慮到這一個(gè)節(jié)點(diǎn)為止，所能形成的最大值。，是經(jīng)過(guò)這個(gè)節(jié)點(diǎn)為止的能形成的最大值的一條支路。 Leetcode[124] Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum. For this problem, a path is defined as any se...
摘要：解題思路用遞歸實(shí)現(xiàn)很簡(jiǎn)單，對(duì)于每個(gè)根節(jié)點(diǎn)，最大深度就等于左子樹(shù)的最大深度和右子樹(shù)的最大深度的較大值。解題思路本題的注意點(diǎn)在于如果某個(gè)根節(jié)點(diǎn)有一邊的子樹(shù)為空，那么它的深度就等于另一邊不為空的子樹(shù)的深度，其他的邏輯與上一題相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...
摘要：棧迭代復(fù)雜度時(shí)間空間遞歸?？臻g對(duì)于二叉樹(shù)思路首先我們分析一下對(duì)于指定某個(gè)節(jié)點(diǎn)為根時(shí)，最大的路徑和有可能是哪些情況。代碼連接父節(jié)點(diǎn)的最大路徑是一二四這三種情況的最大值當(dāng)前節(jié)點(diǎn)的最大路徑是一二三四這四種情況的最大值用當(dāng)前最大來(lái)更新全局最大 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum...
閱讀 2149·2023-04-25 18:49
閱讀 1854·2019-08-30 14:02
閱讀 2657·2019-08-29 17:24
閱讀 3334·2019-08-28 18:10
閱讀 2938·2019-08-28 18:03
閱讀 503·2019-08-26 12:01
閱讀 3322·2019-08-26 11:31
閱讀 1442·2019-08-26 10:29
