Friday, February 6, 2015

LeetCode [105] Construct Binary Tree from Preorder and Inorder Traversal

 105. Construct Binary Tree from Preorder and Inorder Traversal

Medium

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*
the first element of preorder is the root of the tree
since there's no duplicate, the root can be used to separate the left and right trees of the inorder vector
*/

//C++: 20ms
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    unordered_map<int, int> hash;
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        if(n<=0) return NULL;
        for(int i=0; i<n; ++i){
            hash[inorder[i]] = i;
        }
        return helper(preorder, inorder, 0, n-1, 0, n-1);
    }

    TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int lp, int rp, int li, int ri){
        int v = preorder[lp];
        TreeNode *root = new TreeNode(v);
        int i=hash[v];
        int len_left = i-li;
        int len_right = ri-i;
        if(len_left>0) root->left = helper(preorder, inorder, lp+1, lp+len_left, li, i-1);
        if(len_right>0) root->right = helper(preorder, inorder, lp+len_left+1, rp, i+1, ri);
        return root;
    }
};
//Java
/**
 * 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 {
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        if(n==0) return null;
        for(int i=0; i<n; ++i){
            map.put(inorder[i], i);
        }
        
        return helper(preorder, inorder, 0, n-1, 0, n-1);
    }
    
    TreeNode helper(int[] preorder, int[] inorder, int pl, int pr, int il, int ir){
        int v = preorder[pl];
        TreeNode root = new TreeNode(v);
        int indexInorder = map.get(v);
        int lenLeft = indexInorder - il;
        int lenRight = ir - indexInorder;
        if(lenLeft>0)
            root.left = helper(preorder, inorder, pl+1, pl+lenLeft, il, indexInorder-1);
        if(lenRight>0)
            root.right = helper(preorder, inorder, pl+lenLeft+1, pr, indexInorder+1, ir);
        return root;
    }
}
Posted by at
Labels: , , , ,

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)