Algorithm


Problem Nmae: 105. Construct Binary Tree from Preorder and Inorder Traversal

problem Link: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 
 

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.

 

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

Code Examples

#1 Code Example with C Programming

Code - C Programming


typedef struct {
  int *preorder;
  int pre_idx;
  int pre_sz;
  int *inorder;
} data_t;
 
struct TreeNode *make_tree(data_t *data, int start, int end) {
  struct TreeNode *node;
  int i;

  if (start == end) return NULL;
  
  node = malloc(sizeof(struct TreeNode));
  //assert(node);
  node->val = data->preorder[data->pre_idx ++];
  
  i = start;
  while (i  <  end && data->inorder[i] != node->val) i ++;
  
  node->left = make_tree(data, start, i);
  node->right = make_tree(data, i + 1, end);
  
  return node;
}
 
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
  data_t data;
  
  data.preorder = preorder;
  data.pre_idx = 0;
  data.pre_sz = preorderSize;
  data.inorder = inorder;
  
  return make_tree(&data, 0, inorderSize);
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output

x
+
cmd
[3,9,20,null,null,15,7]

#2 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        unordered_map < int, int>m;
        for(int i = 0; i  <  inorder.size(); i++) m[inorder[i]] = i;
        return helper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, m);
    }
    
    TreeNode* helper(vector<int>& preorder, int pStart, int pEnd, vector<int>& inorder, int iStart, int iEnd, unordered_map < int, int>& m) {
        if(pStart > pEnd) return NULL;
        TreeNode* root = new TreeNode(preorder[pStart]);
        int i = m[preorder[pStart]];
        root->left = helper(preorder, pStart + 1, pStart + i - iStart, inorder, iStart, i - 1, m);
        root->right = helper(preorder, pStart + i - iStart + 1, pEnd, inorder, i + 1, iEnd, m);
        return root;
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output

x
+
cmd
[3,9,20,null,null,15,7]

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
  public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map map = new HashMap<>();
    int[] preorderIndex = {0};
    for (int i = 0; i  <  inorder.length; i++) {
      map.put(inorder[i], i);
    }
    return buildTree(preorder, 0, preorder.length - 1, map, preorderIndex);
  }
  
  private TreeNode buildTree(int[] preorder, int left, int right, Map < Integer, Integer> map, int[] preorderIndex) {
    if (left > right) {
      return null;
    }
    int rootVal = preorder[preorderIndex[0]++];
    TreeNode root = new TreeNode(rootVal);
    root.left = buildTree(preorder, left, map.get(rootVal) - 1, map, preorderIndex);
    root.right = buildTree(preorder, map.get(rootVal) + 1, right, map, preorderIndex);
    return root;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
preorder = [-1], inorder = [-1]

Output

x
+
cmd
[-1]

#4 Code Example with Javascript Programming

Code - Javascript Programming


const buildTree = function(preorder, inorder) {
  if(preorder.length === 0 && inorder.length === 0) return null
  const val = preorder[0]
  const node = new TreeNode(val)
  const inIdx = inorder.indexOf(val)
  const leftIn = inorder.slice(0, inIdx)
  const rightIn = inorder.slice(inIdx + 1)
  
  const leftPre = preorder.slice(1, leftIn.length + 1)
  const rightPre = preorder.slice(leftIn.length + 1)
  
  // console.log(leftIn, rightIn, leftPre, rightPre)
  node.left = buildTree(leftPre, leftIn)
  node.right = buildTree(rightPre, rightIn)
  return node
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
preorder = [-1], inorder = [-1]

Output

x
+
cmd
[-1]

#5 Code Example with Python Programming

Code - Python Programming


class Solution(object):
    def buildTree(self, preorder, inorder):
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root
Copy The Code & Try With Live Editor

Input

x
+
cmd
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output

x
+
cmd
[3,9,20,null,null,15,7]

#6 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _105_ConstructBinaryTreeFromPreorderAndInorderTraversal
    {
        public TreeNode BuildTree(int[] preorder, int[] inorder)
        {
            if (preorder.Length == 0 || inorder.Length == 0) return null;
            return BuildTree(preorder, 0, preorder.Length, inorder, 0, inorder.Length);
        }

        private TreeNode BuildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd)
        {
            var root = new TreeNode(preorder[preorderStart]);

            var inorderIndex = inorderStart;
            for (; inorderIndex  <  inorderEnd; inorderIndex++)
                if (inorder[inorderIndex] == preorder[preorderStart])
                    break;

            var leftLength = inorderIndex - inorderStart;
            if (leftLength > 0)
                root.left = BuildTree(preorder, preorderStart + 1, preorderStart + 1 + leftLength, inorder, inorderStart, inorderIndex);
            if (inorderEnd > inorderIndex + 1)
                root.right = BuildTree(preorder, preorderStart + 1 + leftLength, preorderEnd, inorder, inorderIndex + 1, inorderEnd);

            return root;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output

x
+
cmd
[3,9,20,null,null,15,7]
Advertisements

Demonstration


Previous
#104 Leetcode Maximum Depth of Binary Tree Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#106 Leetcode Construct Binary Tree from Inorder and Postorder Traversal Solution in C, C++, Java, JavaScript, Python, C# Leetcode