题目大意：
先序遍历构造二叉树
返回与给定先序遍历 preorder 相匹配的二叉搜索树（binary search tree）的根结点。
(回想一下，二叉搜索树是二叉树的一种，其每个节点都满足以下规则，对于 node.left 的任何后代，值总 < node.val，而 node.right 的任何后代，值总 > node.val。此外，先序遍历首先显示节点的值，然后遍历 node.left，接着遍历 node.right。）
示例：
输入：[8,5,1,7,10,12] 输出：[8,5,10,1,7,null,12]
提示：
1 <= preorder.length <= 100- 先序
preorder中的值是不同的。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1008
解题思路分析：
如果想还原BST二叉搜索树，仅靠一个先序遍历数组是不够的，我们需要另一个中序遍历数组来辅助解题才行。对于BST，中序遍历inorder即是所有节点数字的升序排列，因此我们可以通过preorder数组轻松得到。
这样题目就转化为：已知前序排列和中序排列的前提下，如何还原一个二叉搜索树？关于这个问题，可以参考Leetcode 105那道题目的详细分析：LEETCODE 105. Construct Binary Tree from Preorder and Inorder Traversal 解题思路分析
实现代码：
public TreeNode bstFromPreorder(int[] preorder) {
int[] inorder = Arrays.copyOf(preorder, preorder.length);
Arrays.sort(inorder);
return dfs(preorder,inorder,0,preorder.length-1,0,preorder.length-1);
}
TreeNode dfs(int[] pre, int[] in, int pl, int pr, int il, int ir){
if(pl>pr || il > ir) return null;
TreeNode node = new TreeNode(pre[pl]);
int inIndex=getCountOfLeftTree(in,pre[pl],il,ir);
node.left=dfs(pre,in,pl+1,pl+inIndex-il,il,inIndex-1);
node.right=dfs(pre,in,pl+inIndex-il+1,pr,inIndex+1,ir);
return node;
}
int getCountOfLeftTree(int[] in, int node,int low, int high){
while(low<=high){
int mid=(low+high)/2;
if(in[mid]==node) return mid;
else if(in[mid]<node) low = mid+1;
else high=mid-1;
}
return 0;
}本题解法执行时间为1ms。
Runtime: 1 ms, faster than 25.17% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.
Memory Usage: 37.5 MB, less than 6.00% of Java online submissions for Construct Binary Search Tree from Preorder Traversal.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1008-construct-binary-search-tree-from-preorder-traversal-解题思路分析/