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.
You may assume that duplicates do not exist in the tree.


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


 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
class Solution {
    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);
        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());


# 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])
        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)

No comments:

Post a Comment