[LeetCode] Maximum Binary Tree

xiaoqibTn 發布于2019-08-15 15:59 / 2159人閱讀

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

Example 1:
Input: [3,2,1,6,0,5]
Output: return the tree root node representing the following tree:

Note

The size of the given array will be in the range [1,1000].

Solution

class 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;
    }
}

GPU云服務器云服務器 binary-tree binary-search-tree Maximum LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/69363.html

LeetCode 104 Maximum Depth of Binary Tree 二叉樹最大深度

LeetCode 104 Maximum Depth of Binary Tree難度：Easy 題目描述：找到一顆二叉樹的最深深度。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 ...

PiscesYE 2019-08-16 13:28 評論0 收藏0
[Leetcode-Tree]Binary Tree Maximum Path Sum

摘要：但是本題的難點在于，使用遞歸實現，但是前面的第四種情況不能作為遞歸函數的返回值，所以我們需要定義兩個值，代表單邊路徑的最大值，用于遞歸用于和回路的較大值。 Binary Tree Maximum Path SumGiven a binary tree, find the maximum path sum. For this problem, a path is defined as a...

caige 2019-08-16 10:27 評論0 收藏0
LeetCode[124] Binary Tree Maximum Path Sum

摘要：復雜度思路對于每一節點，考慮到這一個節點為止，所能形成的最大值。，是經過這個節點為止的能形成的最大值的一條支路。 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...

warmcheng 2019-08-16 10:27 評論0 收藏0
[Leetcode-Tree]Maximum / Minimum Depth of Binary T

摘要：解題思路用遞歸實現很簡單，對于每個根節點，最大深度就等于左子樹的最大深度和右子樹的最大深度的較大值。解題思路本題的注意點在于如果某個根節點有一邊的子樹為空，那么它的深度就等于另一邊不為空的子樹的深度，其他的邏輯與上一題相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...

Thanatos 2019-08-16 10:26 評論0 收藏0
[Leetcode] Binary Tree Maximum Path Sum 二叉樹最大路徑和

摘要：棧迭代復雜度時間空間遞歸?？臻g對于二叉樹思路首先我們分析一下對于指定某個節點為根時，最大的路徑和有可能是哪些情況。代碼連接父節點的最大路徑是一二四這三種情況的最大值當前節點的最大路徑是一二三四這四種情況的最大值用當前最大來更新全局最大 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum...

魏憲會 2019-08-14 12:25 評論0 收藏0