Construct Binary Tree from Preorder and Inorder Traversal

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

http://www.lintcode.com/en/problem/construct-binary-tree-from-preorder-and-inorder-traversal/

Discussion

preorder里面第一个就是root的节点值，在inorder里面找到对应节点，之前用于构造左子树，之后的用于构造右子树，同时可以知道用于构造左子树和右子树的节点的个数，从preorder里面相应的取出，递归即可。

Solution

//O(n^2),因为要查找每个node
//O(n*h) space. 因为要copy每个子树O(n),栈空间O(h)
class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        TreeNode *root = NULL;
        if(preorder.size()>0 && inorder.size()>0) {
            root = new TreeNode(preorder[0]);
            int idx = -1;
            int tgt = preorder[0];
            for(int i=0; i<inorder.size(); i++) {
                if(tgt ==  inorder[i]) {
                    idx = i;
                    break;
                }
            }
            if(idx == -1) {
                return NULL;
            }
            vector<int> preorderL(idx), preorderR(inorder.size()-1-idx); vector<int> inorderL(idx), inorderR(inorder.size()-1-idx);

            copy(preorder.begin()+1, preorder.begin()+idx+1, preorderL.begin());
            copy(inorder.begin(), inorder.begin()+idx, inorderL.begin());
            root->left = buildTree(preorderL, inorderL);
            copy(preorder.begin()+idx+1, preorder.end(), preorderR.begin());
            copy(inorder.begin()+idx+1, inorder.end(), inorderR.begin());
            root->right = buildTree(preorderR, inorderR);
        }
        return root;
    }
};

下面发方法是O(h)space，不copy构造新的preorder和inorder，而是update起始位置和终止位置

class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        if(preorder.size()==0 || preorder.size() != inorder.size() ) return NULL;
        int n = preorder.size();
        TreeNode *root = buildSubtree(preorder, inorder, 0, n-1, 0,n-1);
        return root;

    }
    TreeNode *buildSubtree(vector<int> &preorder, vector<int> &inorder, 
    int s1, int e1, int s2, int e2) {
        if(s1 > e1 || s2 > e2) return NULL;
        TreeNode *root = new TreeNode(preorder[s1]);
        int idx = find(inorder, s2, e2, preorder[s1]);
        if(idx == -1) return NULL;
        int len1 = idx-s2;
        root->left = buildSubtree(preorder, inorder, s1+1, s1+len1, s2, idx-1);
        root->right = buildSubtree(preorder, inorder, s1+len1+1, e1, idx+1, e2);
        return root;
    }
    int find(vector<int> inorder, int start, int end, int target) {
        for(int i=start; i<=end; i++) {
            if(inorder[i] == target) {
                return i;
            }
        }
        return -1;
    }
};

一个递归的写法：

// Time:  O(n)//因为用了hash查找
// Space: O(h)
class Solution {
    /**
     *@param preorder : A list of integers that preorder traversal of a tree
     *@param inorder : A list of integers that inorder traversal of a tree
     *@return : Root of a tree
     */
public:
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        // write your code here
        unordered_map<int, int> inMap;
        if(preorder.size() == 0 || preorder.size() != inorder.size()) 
            return NULL;
        for(int i=0; i<inorder.size(); i++) {
            inMap[inorder[i]] = i;
        }
        return buildTreeHelper(preorder, 0, preorder.size()-1, 
        inorder, 0, inorder.size()-1, inMap);
    }
    TreeNode *buildTreeHelper(vector<int> &preorder, int pre_s, int pre_e,
    vector<int> &inorder, int in_s, int in_e, unordered_map<int, int> &inMap) {
        if(pre_e >= pre_s && in_e>= in_s) {//传的是n-1，这里有可能=
            TreeNode *root = new TreeNode(preorder[pre_s]);
            int idx = inMap[preorder[pre_s]];
            int len = idx - in_s;
            root->left = buildTreeHelper(preorder, pre_s+1, pre_s+len,
            inorder, in_s, idx-1, inMap);
            root->right = buildTreeHelper(preorder, pre_s+1+len, pre_e,
            inorder, idx+1, in_e, inMap);
            return root;
        }
        return NULL;
    }
};