一.题目介绍
1.题目来源
链接：LeetCode
2.题目
给定一个不重复的整数数组nums。 最大二叉树可以用下面的算法从nums递归地构建: 创建一个根节点，其值为nums中的最大值。 递归地在最大值左边的子数组前缀上构建左子树。 递归地在最大值右边的子数组后缀上构建右子树。 返回nums构建的最大二叉树 。
二.具体实现
1.实现思路
定义l为左节点，r为右节点，找终止条件：当l>r时，说明数组中已经没元素了，自然当前返回的节点为null。 每一级递归返回的信息是什么：返回的应该是当前已经构造好了最大二叉树的root节点。 一次递归做了什么：找当前范围为[l,r]的数组中的最大值作为root节点，然后将数组划分成[l,bond-1]和[bond+1,r]两段，并分别构造成root的左右两棵子最大二叉树。
2.实现代码
1)自己的实现方式
public TreeNode constructMaximumBinaryTree(int[] nums) { return maxTree(nums, 0, nums.length - 1); } public TreeNode maxTree(int[] nums, int l, int r){ if (l > r){ return null; } //找到当前最大值的索引 int bond = findMax(nums, l, r); //此时bond为根节点 TreeNode root = new TreeNode(nums[bond]); root.left = maxTree(nums, l, bond - 1); root.right = maxTree(nums, bond + 1, r); return root; } //找最大值的索引 public int findMax(int[] nums, int l, int r){ int max = Integer.MIN_VALUE, maxIndex = l; for(int i = l; i <= r; i++){ if(max < nums[i]){ max = nums[i]; maxIndex = i; } } return maxIndex; } 复制代码
2)题友的解题思路及实现代码
使用递归法，但是比我的简洁很多，下面是具体步骤：
1.二叉树的根是数组中的最大元素。
2.左子树是通过数组中最大值左边部分构造出的最大二叉树。
3.右子树是通过数组中最大值右边部分构造出的最大二叉树。
3.运行结果
三.题后思考
二叉树的题目还是很抽象，之前记得有个动态二叉树的生成网站现在已经关闭了，试用了好几款生成二叉树的开源框架感觉不是很好，不然有动态图理解起来会更加容易一些。做算法题其实空想是没用的而且效率不高，要有图协助才能事半功倍，另外题解的技巧也需要慢慢积累的，不要急着想一天两天就能完美解题的。
