Leetcode Construct Binary Tree from Preorder and Inorder Traversal problem solution

YASH PAL,

In this Leetcode Construct Binary Tree from Preorder and Inorder Traversal problem solution we have Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

Leetcode Construct Binary Tree from Preorder and Inorder Traversal problem solution

Problem solution in Python.

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
  
        if not preorder:
            return None
        
        ind = {inorder[i]:i for i in range(len(inorder))}
        
        def build(low,high):
            if low>high:
                return None
            val = next(nextnode)
            root = TreeNode(val)
            root.left = build(low,ind[val]-1)
            root.right = build(ind[val]+1,high)
            return root
        
        nextnode = iter(preorder)
        return build(0,len(inorder)-1)

Problem solution in Java.

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        List<Integer> pre = new ArrayList();
        for (int i : preorder) {
            pre.add(i);
        }
        return helper(pre, map, 0, inorder.length - 1);
    }
    
    private TreeNode helper(List<Integer> pre, Map<Integer, Integer> map, int start, int end) {
        if (start > end) {
            return null;
        } else if (start == end) {
            return new TreeNode(pre.remove(0));
        } else {
            int val = pre.remove(0);
            TreeNode root = new TreeNode(val);
            root.left = helper(pre, map, start, map.get(val) - 1);
            root.right = helper(pre, map, map.get(val) + 1, end);
            return root;
        }
    }
}

Problem solution in C++.

class Solution {
public:
    TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
        unordered_map<int, int> pos;
        int n = pre.size();
        for (int i = 0; i < n; i++) {
            pos[in[i]] = i;
        }
        TreeNode* root = NULL;
        for (int i = 0; i < n; i++) {
            int num = pre[i], p = pos[num];
            TreeNode* tr = new TreeNode(num);
            if (i == 0) {
                root = tr;
                continue;
            }
            TreeNode* node = root, *prev = NULL;
            while (node) {
                prev = node;
                if (pos[node->val] > p) node = node->left;
                else  node = node->right;
            }
            node = tr;
            if (pos[prev->val] > p) prev->left = tr;
            else    prev->right = tr;
        }
        return root;
    }
};

Problem solution in C.

int *g_preorder;
int g_preorderSize;
int *g_inorder;
int g_inorderSize;
int g_index[10000];
int g_preIndex = 0;
void buildChildTree(int inStart, int inEnd, struct TreeNode **root) {

    if (g_preIndex >= g_inorderSize) {
        return;
    }
    *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    int val = g_preorder[g_preIndex];
    (*root)->val = val;
    (*root)->left = NULL;
    (*root)->right = NULL;
    if (g_index[val + 3000] > inStart) {
        (g_preIndex) += 1;
        buildChildTree(inStart, g_index[val + 3000] - 1, &((*root)->left));
    }
    if(g_index[val + 3000] < inEnd) {
        (g_preIndex) += 1;
        buildChildTree(g_index[val + 3000] + 1, inEnd , &((*root)->right));
    }

    
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    struct TreeNode *root;
    int preIndex = 0;
    if (preorderSize == 0) {
        return NULL;
    }
    for (int i = 0; i < inorderSize; i++) {
        g_index[inorder[i] + 3000] = i;
    }
    g_preorder = preorder;
    g_preorderSize = preorderSize;
    g_inorder = inorder;
    g_inorderSize = inorderSize;
    g_preIndex = 0;
    buildChildTree(0, inorderSize - 1, &root);
    return root;
}

coding problems