[LeetCode] Maximum Binary Tree

xiaoqibTn 发布于2019-08-15 15:59 / 2131人阅读

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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 二叉树最大路径和

摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路首先我们分析一下对于指定某个节点为根时，最大的路径和有可能是哪些情况。代码连接父节点的最大路径是一二四这三种情况的最大值当前节点的最大路径是一二三四这四种情况的最大值用当前最大来更新全局最大 Binary Tree Maximum Path Sum Given a binary tree, find the maximum path sum...

魏宪会 2019-08-14 12:25 评论0 收藏0