Amazon
2020-05-24
1008. Construct Binary Search Tree from Preorder Traversal
Question:
Return the root node of a binary search tree that matches the given preorder
traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left
has a value <
node.val
, and any descendant of node.right
has a value >
node.val
. Also recall that a preorder traversal displays the value of the node
first, then traverses node.left
, then traverses node.right
.)
It’s guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Constraints:
1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
- The values of
preorder
are distinct.
Solution:
Becuase it’s a binary search tree, all the value larger than the first node are on the right. Same for the value smaller than the first node. Thus, set a threshold for the maximum value and use recursion to assign the value to left or right.
/**
* 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;
* }
* }
*/
class Solution {
int index = 0;
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) return new TreeNode();
return bstHelper(preorder, Integer.MAX_VALUE);
}
public TreeNode bstHelper(int[] preorder, int max) {
if (index == preorder.length || preorder[index] > max) return null;
TreeNode curr = new TreeNode(preorder[index++]);
curr.left = bstHelper(preorder, curr.val);
curr.right = bstHelper(preorder, max);
return curr;
}
}
In addition, using the same idea, we could use two pointers to record the lower bound and upper bound of the traversal.
/**
* 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;
* }
* }
*/
class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) return new TreeNode();
return bstHelper(preorder, 0, preorder.length - 1);
}
public TreeNode bstHelper(int[] preorder, int start, int end) {
if (start > end) return null;
int currval = preorder[start];
TreeNode curr = new TreeNode(currval);
int i;
for (i = start; i <= end; i++) {
if (preorder[i] > currval) {
break;
}
}
curr.left = bstHelper(preorder, start + 1, i - 1);
curr.right = bstHelper(preorder, i, end);
return curr;
}
}