LeetCode 654 Maximum Binary Tree

一份执着✘

修改于 2019-12-30 16:56:36

3240

修改于 2019-12-30 16:56:36

文章被收录于专栏：赵俊的Java专栏赵俊的Java专栏

题意

给定一个整数数组，生成一棵 最大二叉树，规则是数组中的最大值为根节点，然后分割出最大值左侧的子数组再构造 最大二叉树，最大值的右侧也构造成 最大二叉树。

例 :

输入: [3,2,1,6,0,5]
输出: 返回表示以下树的根节点:

      6
    /   \
   3     5
    \    / 
     2  0   
       \
        1

解法

根据题意，是经典的分而治之的题目，用递归就可以很简单的实现：

public TreeNode constructMaximumBinaryTree(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return null;
        }

        int max = Integer.MIN_VALUE;
        int maxIndex = -1;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            if (num > max) {
                max = num;
                maxIndex = i;
            }
        }
        TreeNode node = new TreeNode(max);
        node.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxIndex));
        node.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxIndex + 1, len));
        return node;
    }

Runtime: 6 ms, faster than 69.99% of Java online submissions for Maximum Binary Tree. Memory Usage: 39.1 MB, less than 88.96% of Java online submissions for Maximum Binary Tree.

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-03-252，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树