题目大意:
先序遍历构造二叉树
返回与给定先序遍历 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.
本网站文章均为原创内容,并可随意转载,但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1008-construct-binary-search-tree-from-preorder-traversal-解题思路分析/