LeetCode刷题【1008】前序遍历构造二叉搜索树

返回与给定前序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。

(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，前序遍历首先显示节点 node 的值，然后遍历 node.left，接着遍历 node.right。）

题目保证，对于给定的测试用例，总能找到满足要求的二叉搜索树。

示例：

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

提示：

• 1 <= preorder.length <= 100
• 1 <= preorder[i] <= 10^8
• preorder 中的值互不相同

题解

思路和LeetCode刷题【剑指 Offer 33】二叉搜索树的后续遍历序列一样了，根据前序遍历的特性，一样的第一位为根节点，后面的序列中，比根节点小的为左子树上的节点，比根节点大的为右子树上的节点

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * 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 bstFromPreorder(int[] preorder) {
        return buildTree(preorder,0,preorder.length-1);
    }



    private TreeNode buildTree(int[] preorder,int left ,int right){
        //必要判断条件，如果区间范围不成立，表名没有这个节点
        if (left > right || left < 0 || right < 0) return null;
        //根据前序遍历的特性，该连续数组的第一位为这个树的根节点
        TreeNode node = new TreeNode(preorder[left]);
        if (left==right){
            return node;
        }
        //首位为根节点，往后进一格，处理子节点
        left++;
        //预设一个-1标记
        int rightStart = -1;
        for (int i = left; i <= right ; i++) {
            if (preorder[i]>node.val){
                //如果当前节点比根节点大
                //那么从当前节点开始，往后的都是右子节点
                rightStart = i;
                break;
            }
        }
        //如果没有找到右子节点的话，因为之前预设了-1，需要额外判断下右子节点的开始位置
        //不然还是-1，
        //没有找到右子节点的区间的话，说明左子节点区间应该为从left到right都是
        if (rightStart == -1){
            rightStart = right+1;
        }
        //分别拿出左右子节点区间继续判断处理
        node.left = buildTree(preorder,left,rightStart-1);
        node.right = buildTree(preorder,rightStart,right);
        return node;
    }
}
//leetcode submit region end(Prohibit modification and deletion)