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.
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; }