LEETCODE 1008. Construct Binary Search Tree from Preorder Traversal 解题思路分析

题目大意:

先序遍历构造二叉树

返回与给定先序遍历 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. 1 <= preorder.length <= 100
  2. 先序 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.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1008-construct-binary-search-tree-from-preorder-traversal-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。