前序遍历构造二叉搜索树

给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点， Node.left 的任何后代的值 严格小于 Node.val , Node.right 的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

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

一、解题思路

BST无重复节点,给出树的先序追历结果,重建整颗树并返回头节点,如果它是搜素二叉树而且无重复,那么得到一个先序遍历的结果,它是可以还原出唯一的树出来的,如果它有重复那就不唯一了

递归的思想定义函数f(L, R):从L..R范围是一棵树的先序遍历结果,请建出整颗树把头部node返回
主函数: f(0, 8),头节点5,从1位置开始比5小的都是左树,剩下的都是比5大的右树,剩下的递归

特殊边界

左边没有比5小的,返回null, 右边f(1, 2)
一个X节点不一定都有左树,右树

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if(preorder==null||preorder.length==0){
            return null;
        }
        int n=preorder.length;
        return process(preorder,0,n-1);
    }
    public TreeNode process(int[] preorder,int l,int r){
        if(l>r){
            return null;
        }
        TreeNode head=new TreeNode(preorder[l]);
        int less=l;
        for(;less<=r;less++){
            if(preorder[l]<preorder[less]){
                break;
            }
        }
        head.left=process(preorder,l+1,less-1);
        head.right=process(preorder,less,r);
        return head;
    }
}

二、使用单调栈优化

我们在递归中找离L最近比L大的数,
可以用单调栈生成nearBig数组,记录每个i位置最近比i位置大的数

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        if(preorder==null||preorder.length==0){
            return null;
        }
        int n=preorder.length;
        int[] stack=new int[preorder.length];
        int[] nearBig=new int[n];
        for(int i=0;i<n;i++){
            nearBig[i]=-1;
        }
        int size=0;
        for(int i=0;i<n;i++){
            while(size!=0&&preorder[stack[size-1]]<preorder[i]){
                nearBig[stack[--size]]=i;
            }
            stack[size++]=i;
        }
        return process(preorder,0,n-1,nearBig);
    }
    public TreeNode process(int[] preorder,int l,int r,int[] nearBig){
        if(l>r){
            return null;
        }
        
        int less=(nearBig[l]==-1||nearBig[l]>r)?r+1:nearBig[l];
        int less=l;
        for(;less<=r;less++){
            if(preorder[l]<preorder[less]){
                break;
            }
        }
        TreeNode head=new TreeNode(preorder[l]);
        head.left=process(preorder,l+1,less-1,nearBig);
        head.right=process(preorder,less,r,nearBig);
        return head;
    }
}