654. 最大二叉树

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

二叉树的根是数组 nums 中的最大元素。
左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。
右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归

class Solution {

    private int[] nums;

    private TreeNode solve(int l, int r) {
        if (l > r) {
            return null;
        }
        int index = maxIndex(l, r);
        TreeNode root = new TreeNode(nums[index]);
        root.left = solve(l, index - 1);
        root.right = solve(index + 1, r);
        return root;
    }

    private int maxIndex(int l, int r) {
        int ans = l;
        for (int i = l; i <= r; ++i) {
            if (nums[i] > nums[ans]) {
                ans = i;
            }
        }
        return ans;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        this.nums = nums;
        return solve(0, nums.length - 1);
    }

}

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

线段树

import java.util.Arrays;

class Solution {

    private int[] nums;

    private SegmentTree segmentTree;

    private TreeNode solve(int l, int r) {
        if (l > r) {
            return null;
        }
        int index = segmentTree.query(l, r, 1, nums.length, 1);
        TreeNode root = new TreeNode(nums[index]);
        root.left = solve(l, index);
        root.right = solve(index + 2, r);
        return root;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        this.segmentTree = new SegmentTree(nums);
        this.nums = nums;
        return solve(1, nums.length);
    }
}


class SegmentTree {
    private int[] original;
    private int[] max;

    public SegmentTree(int[] original) {
        this.original = original;
        this.max = new int[original.length << 2 | 1];
        Arrays.fill(this.max, Integer.MIN_VALUE);
        this.build();
    }

    private void pushUp(int rt) {
        if (original[max[rt << 1]] > original[max[rt << 1 | 1]]) {
            max[rt] = max[rt << 1];
        } else {
            max[rt] = max[rt << 1 | 1];
        }
    }

    private void build(int l, int r, int rt) {
        if (l == r) {
            max[rt] = l - 1;
            return;
        }
        int mid = (l + r) >> 1;
        if (l <= mid) {
            build(l, mid, rt << 1);
        }

        if (mid < r) {
            build(mid + 1, r, rt << 1 | 1);
        }
        pushUp(rt);
    }

    private int maxIndex(int index1, int index2) {
        if (index1 == -1) {
            return index2;
        }
        if (index2 == -1) {
            return index1;
        }
        return original[index1] > original[index2] ? index1 : index2;
    }

    public int query(int L, int R, int l, int r, int rt) {
        if (L <= l && R >= r) {
            return max[rt];
        }
        int index = -1;
        int mid = (l + r) >> 1;
        if (L <= mid) {
            int idx = query(L, R, l, mid, rt << 1);
            index = maxIndex(index, idx);
        }

        if (mid < R) {
            int idx = query(L, R, mid + 1, r, rt << 1 | 1);
            index = maxIndex(index, idx);
        }
        return index;
    }

    private void build() {
        build(1, original.length, 1);
    }
}

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