1、题目
image.png
2、分析
大神曾经说过，递归算法，其实就是把题目的要求细化，搞清楚根节点应该做什么，然后剩下的事情抛给前/中/后序的遍历框架就行了
3、我自己的代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
int maxIndex = getMaxIndex(nums); //查找最大值
if (maxIndex == -1) return null;
int length = nums.length;
int[] leftNums = new int[maxIndex];
int[] rightNums = new int[length - maxIndex - 1];
for (int i = 0; i < maxIndex; i ++){
//把左边的数组重新赋值
leftNums[i] = nums[i];
}
int j = 0;
for (int i = maxIndex + 1; i < length; i++){
//把右边的数组重新赋值
rightNums[j] = nums[i];
j++;
}
//递归构造
TreeNode left = constructMaximumBinaryTree(leftNums);
TreeNode right = constructMaximumBinaryTree(rightNums);
TreeNode node = new TreeNode(nums[maxIndex], left, right);
return node;
}
private int getMaxIndex(int[] nums){
int tmp = 0;
int index = 0;
int length = nums.length;
if (length == 0) return -1;
for(int i = 0; i < length; i ++){
if (nums[i] > tmp){
tmp = nums[i];
index = i;
}
}
return index;
}
}
某大神的代码，这样占用内存空间比较少。因为我还需要给左右子树的数组重新赋值。看看大神代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}
private TreeNode build(int[] nums, int lo, int hi){
if (lo > hi) return null;
int maxVal = Integer.MIN_VALUE;
int index = -1;
for(int i = lo; i <= hi; i ++){
if (nums[i] > maxVal){
maxVal = nums[i];
index = i;
}
}
TreeNode root = new TreeNode(maxVal);
root.left = build(nums, lo, index - 1);
root.right = build(nums, index + 1, hi);
return root;
}
}
