LeetCode:1008. 前序遍历构造二叉搜索树

目录

题目描述:

代码:

第一种:

第二种:

第三种:分治法

题目描述:

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

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

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

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

示例 1：

输入：preorder = [8,5,1,7,10,12]
输出：[8,5,10,1,7,null,12]

示例 2:

输入: preorder = [1,3]
输出: [1,null,3]

代码:

第一种:

从左到右依次建立二叉搜索树

public TreeNode bstFromPreorder1(int[] preorder) {
        TreeNode root=new TreeNode(preorder[0]);
        for(int i=1;i<preorder.length;i++){
            int val=preorder[i];
            insert1(root,val);
        }
        return root;
    }
    public TreeNode insert1(TreeNode root,int val){
        if(root==null){
            return new TreeNode(val);
        }
        if(val<root.val){
            root.left=insert1(root.left,val);
        }else{
            root.right=insert1(root.right,val);
        }
        return root;
        }

第二种:

上限法

public TreeNode bstFromPreorder2(int[] preorder) {
        return insert(preorder,Integer.MAX_VALUE);
    }
    int i=0;
    public TreeNode insert(int[] preorde,int max){
        //递归结束的条件
        if(preorde.length==0){
            return null;
        }
        int val=preorde[i];
        //如果超出上限,返回null
        if(val>max){
            return null;
        }
        //创建节点
        TreeNode root=new TreeNode(val);
        i++;
        //没超过上限,设置其子孩子,设置完返回
        //preorder,5(自身值)
        root.left=insert(preorde,val);
        //preorder,8(上一个节点值)
        root.right=insert(preorde,max);
        return root;
    }

第三种:

//解法3:分治法
//8,5,1,7,10,12
/*
* 根:8
* 左:5,1,7
* 右:10,12
*
* 根:5
* 左:1
* 右:7
*
* 根:10
* 左:null
* 右:12
* */

 public TreeNode bstFromPreorder(int[] preorder) {
        return partition(preorder,0,preorder.length-1);

    }
    private TreeNode partition(int[] preorder,int start,int end){
        if(start>end){
            return null;
        }
        TreeNode root=new  TreeNode(preorder[start]);
        int index=start+1;
        while(index<=end){
            if(preorder[index]>preorder[start]){
                break;
            }
            index++;
        }
        //index 是右子树的起点
        root.left=partition(preorder,start+1,index-1);
        root.right=partition(preorder,index,end);
        return root;
    }