Problem: Construct BST from given preorder traversal
这是 Facebook 的一道面试题,这个贴子讲得还行。
http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/
思路
这道题的思路和上一题是一样的,就是通过 preorder 的序列和 BST 的性质来确定一个 Tree
我们可以看出来,第一个元素肯定是一个根,那么我们找下一个比目前的根大的元素,那么从它开始就是右子树,左边的就是左子树。然后用递归构建整个 Tree。
递归的退出条件:
start == end
,说明已经是叶子了,直接返回就行
复杂度
Time:
O(n)
,遍历整个数组
/**
* Created by yang on 12/29/16.
*/
public class PreorderToBST {
// TreeNode class
public static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) {
this.val = x;
}
}
// convert function
public static TreeNode convertBST(int[] preorder) {
return helper(preorder, 0, preorder.length - 1);
}
// helper function, call recursively
private static TreeNode helper(int[] preorder, int start, int end) {
if (start == end) {
TreeNode node = new TreeNode(preorder[start]);
return node;
}
int rootVal = preorder[start];
int rootIndex = findIndex(preorder, rootVal, start, end);
TreeNode root = new TreeNode(rootVal);
root.left = helper(preorder, start + 1, rootIndex - 1);
root.right = helper(preorder, rootIndex, end);
return root;
}
// find index
private static int findIndex(int[] preorder, int rootVal, int start, int end) {
for (int i = start; i <= end; i++) {
if (preorder[i] > rootVal) {
return i;
}
}
return -1;
}
// print function
private static void printTree(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
printTree(root.left);
printTree(root.right);
}
// test, main function
public static void main(String[] args) {
int[] preorder = new int[]{6, 4, 3, 5, 10, 7, 11};
TreeNode root = convertBST(preorder);
System.out.println("Print preorder: ");
printTree(root);
}
}
PreviousProblem 106: Construct Binary Tree from Inorder and Postorder TraversalNextProblem 285: Inorder Successor in BST
Last updated
Was this helpful?