leetcode Question 21: Construct Binary Tree from Preorder and Inorder Traversal

Construct Binary Tree from Preorder and Inorder Traversal

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

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

Analysis:

The idea is similar to the previous question. Just be careful with the order of dividing the vector, and the order of preorder root.

Code(C++):

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findId(int n, vector<int> &inorder){
        for (int i=0;i<inorder.size();i++){
            if (inorder[i] == n) return i;
        }
    }

    TreeNode* bst(vector<int> &preorder, int &mid, vector<int> &inorder, int st, int ed){
        if (st>ed || preorder.size()==mid){
            return NULL;
        }
        TreeNode* root = new TreeNode(preorder[mid]);
        int idx = findId(preorder[mid], inorder);
        mid++;
        root->left = bst(preorder, mid, inorder, st, idx-1);
        root->right = bst(preorder, mid, inorder, idx+1, ed);
        return root;
    }
    
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        int mid = 0;
        return bst(preorder, mid, inorder, 0, inorder.size());
    }
};

Code(Python):

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param preorder, a list of integers
    # @param inorder, a list of integers
    # @return a tree node
    def bst(self, preorder, inorder):
        if len(preorder) == 0 or len(inorder) == 0:
            return None
        root = TreeNode(preorder[0])
        idx = inorder.index(preorder[0])
        preorder.pop(0)
        root.left = self.bst(preorder, inorder[0:idx]) 
        root.right = self.bst(preorder, inorder[idx+1:])
        return root
    
    
    def buildTree(self, preorder, inorder):
        return self.bst(preorder, inorder)