Construct Binary Search Tree from Preorder Traversal
从preorder建bst.
这个题要先通过排序找到inorder, 因为inorder中的root在中间, 所以知道左右就是leaf, 通过记录leaf的value, 知道位置, 然后就可以确定bst了.
/**
* 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) {
int[] inorder = new int[preorder.length];
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < preorder.length; i++) {
inorder[i] = preorder[i];
}
Arrays.sort(inorder);
for(int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return toTree(map, preorder, inorder, 0, inorder.length - 1);
}
int preIndex = 0;
private TreeNode toTree(Map<Integer, Integer> map, int[] pre, int[] in, int start, int end) {
if(start > end)
return null;
TreeNode root = new TreeNode(pre[preIndex]);
int inIndex = map.get(pre[preIndex]);
preIndex++;
root.left = toTree(map, pre, in, start, inIndex - 1);
root.right = toTree(map, pre, in, inIndex + 1, end);
return root;
}
}