654. 最大二叉树

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的 最大二叉树 。

示例
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

思路一：递归 求出一段范围内的最大值，如此反复

class Solution {
    
    public TreeNode constructMaximumBinaryTree(int[] nums) {
       if(nums==null) return null;
       return findRoot(nums,0,nums.length);
    }

    private TreeNode findRoot(int[] nums,int l,int r) {

        //递归结束条件
        if(l==r) return null;

        int maxIdx = l;//最大值索引
        //寻找最大值索引
        for(int i = l; i < r;i++){
            if(nums[i] > nums[maxIdx]) maxIdx = i;
        }
        //创建节点
        TreeNode root = new TreeNode(nums[maxIdx]);
        root.left =  findRoot(nums,l,maxIdx);
        root.right =  findRoot(nums,maxIdx+1,r);
        return root;
    }

}

变种题：返回一个数组，数组里面存着每个结点的父结点的索引(如果没有父结点，就存-1); 其他跟上面一样

思路：单调栈（单调递减栈），利用栈求出每个索引位的值得左右第一个比它大的值得索引放进数组， 然后遍历数组，整理出每个结点的父结点的索引放进结果数组

    public TreeNode parentIndxes(int[] nums) {
       if(nums==null||nums.length==0) return null;
       
       /**
        1. 扫描一遍所有的元素
        2. 保持栈从栈底到栈顶是单调递减的
        */
        int[] lis = new int[nums.length];//左边比我大的
        int[] ris = new int[nums.length];//右边比我大的
        
        Stack<Integer> stack = new Stack<>();
        //初始化
        for(int i = 0;i<nums.length;i++) {
            lis[i] = -1;
            ris[i] = -1;
        }

        for(int i = 0;i<nums.length;i++) {

           //1. 栈不为空 且 当前值 大于 栈顶索引对应的值
           while(!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                /**
                1.弹出栈顶索引
                2.设置栈顶索引位的值的 右边第一个比她大的值 的索引为 i
                 */
                ris[stack.pop()] = i;
           }

           //2. 来到这里说明 nums[i] < nums[stack.peek()]
           if(!stack.isEmpty()) {//栈不为空，设置i位置左边第一个比它大的值索引为栈顶索引
                lis[i] = stack.peek();
           }

           //入栈
           stack.push(i);
           
        }

        int[] pis = new int[nums.length];
        for(int i = 0;i < pis.length;i++) {

            //i位置的是根结点
            if(lis[i]==-1 && ris[i]==-1) {
               //根结点没有父结点
               pis[i] = -1;
               continue;
            }

            //左边没有比我大的
            if(lis[i]=-1) {
                pis[i] = ris[i];
            }else if(ris[i]==-1) {//右边没有比我大的
                pis[i] = lis[i];
            }else if(nums[lis[i]] < nums[ris[i]]){//左边小于右边
                 pis[i] = lis[i];
            }else {//右边小于左边
                 pis[i] = ris[i];
            }

        }

        return pis;
    }