LeetCode 654. 最大二叉树

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;
    }
}

大神的解析：
https://mp.weixin.qq.com/s/OlpaDhPDTJlQ5MJ8tsARlA