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

#头条创作挑战赛#

题目：

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

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

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

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

示例 1：

image.png

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

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

示例 2:

输入: preorder = [1,3]

输出: [1,null,3]

提示：

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

思路：

由于树是「二叉搜索树」，我们知道「二叉搜索树」的中序遍历的结果是有序序列。我们可以对「前序遍历」的结果 排序 得到「中序遍历」的结果。于是问题就转换成为 105. 从前序与中序遍历序列构造二叉树，该题也是一道非常经典的二叉树问题.

作者：力扣 (LeetCode)

链接：https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/solutions/3596/jian-kong-er-cha-shu-by-leetcode/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

java代码：

/**
 * 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;
 *     }
 * }
 */
 import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {

    public TreeNode bstFromPreorder(int[] preorder) {
        int len = preorder.length;
        int[] inorder = new int[len];
        System.arraycopy(preorder, 0, inorder, 0, len);
        Arrays.sort(inorder);

        return dfs(preorder, inorder);
    }

    private TreeNode dfs(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[0]);
        if (preorder.length == 1) {
            return root;
        }

        int pos = 0;
        for (; pos < inorder.length; pos++) {
            if (inorder[pos] == preorder[0]) {
                break;
            }
        }

        int[] leftIn = new int[pos];
        int[] rightIn = new int[inorder.length - pos - 1];
        int[] leftPre = new int[pos];
        int[] rightPre = new int[inorder.length - pos - 1];

        System.arraycopy(inorder, 0, leftIn, 0, pos);
        System.arraycopy(inorder, pos + 1, rightIn, 0, inorder.length - pos - 1);
        System.arraycopy(preorder, 1, leftPre, 0, pos);
        System.arraycopy(preorder, pos + 1, rightPre, 0, inorder.length - pos - 1);

        root.left = dfs(leftPre, leftIn);
        root.right = dfs(rightPre, rightIn);
        return root;
    }
}