関小君刷题记

题目大意：

最大二叉树

给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

1. 二叉树的根是数组中的最大元素。
2. 左子树是通过数组中最大值左边部分构造出的最大二叉树。
3. 右子树是通过数组中最大值右边部分构造出的最大二叉树。

通过给定的数组构建最大二叉树，并且输出这个树的根节点。

示例 ：

输入：[3,2,1,6,0,5]
输出：返回下面这棵树的根节点：
   6
 /   \
3     5
 \   /
  2 0
   \
    1

提示：

1. 给定的数组的大小在 [1, 1000] 之间。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=654

解题思路分析：

这道题其实难度并不大，一开始我想复杂了，花了大量时间在考虑如何快速找到每个区间内的最大值，后来发现数据规模不大，因此每一次在区间内暴力搜索最大值即可。

解题时我们定义一个递归函数，函数的参数包括原始数组，当前节点所在范围的左边界以及右边界。起始时，二叉树的根节点在数组全范围内[0, length-1]。递归中，在该范围内找到一个最大值，并记录该最大值所在下标maxIndex，利用该最大值构建一个节点对象。另外该节点对象的左子节点在当前范围left到maxIndex-1区间，递归至子方法求解即可，同理右子节点在区间maxIndex+1到right区间内。当前节点对象为当前递归的返回值。递归的终止条件为左区间大于右区间。

实现代码：

public TreeNode constructMaximumBinaryTree(int[] nums) {
    return help(nums, 0, nums.length-1); // 递归构建二叉树
}

TreeNode help(int[] nums, int left, int right){
    if(left>right) return null; // 非法区间，返回null
    int maxIndex=max(nums,left,right); // 找到区间内最大值所在下标
    TreeNode node=new TreeNode(nums[maxIndex]); // 利用区间最大值构建当前节点
    node.left=help(nums,left,maxIndex-1); // 递归构建左子节点
    node.right=help(nums,maxIndex+1,right); // 递归构建右子节点
    return node; // 返回当前节点
}
// 找到区间内最大值
int max(int[] nums, int left,int right){
    int maxIndex=left;
    for(int i=left;i<=right;i++){
        if(nums[i]>nums[maxIndex]){
            maxIndex=i;
        }
    }
    return maxIndex;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 91.68% of Java online submissions for Maximum Binary Tree.

Memory Usage: 39.7 MB, less than 38.40% of Java online submissions for Maximum Binary Tree.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-654-maximum-binary-tree-解题思路分析/