LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

Problem

LeetCode 1008. Construct Binary Search Tree from Preorder Traversal

1. 题目简述

给出一棵BST树的前序遍历的顺序，恢复这棵树。例如：

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

Constraints:

1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
The values of preorder are distinct.

2. 算法思路

中序遍历+前序遍历

这道题和LeetCode 105很像，只不过105中给出的是一棵二叉树的前序和中序遍历，对于BST树来说，其中序遍历就是其所有元素从小到大的排列。

第一种做法更加简洁一些。中序遍历的顺序是”中->左子树->右子树”，也就是说从第二个元素开始，到左子树结束，其中间的数都比“中”要小，所以并不需要通过中序遍历找左右子树。

第二种做法就是重排列一下数组，然后以前序遍历和中序遍历的顺序重新construct整棵树。这种做法麻烦的地方在于需要注意很多index，一不小心就会出很大的错。

3. 解法

1. 简洁版，不找中序遍历序列

/**
 * 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 start, int end) {
        if (start > end) {
            return null;
        }

        int temp = end;
        while (preorder[temp] > preorder[start]) {
            temp--;
        }

        TreeNode node = new TreeNode(preorder[start]);
        node.left = buildTree(preorder, start + 1, temp);
        node.right = buildTree(preorder, temp + 1, end);

        return node;
    }
}

2. 麻烦版本（代码见LeetCode 105 ）