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;
    }
}

/**

* 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;

}

Construct Binary Search Tree from Preorder Traversal

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.

Categories

Tags