Construct Binary Tree from Preorder and Inorder Traversal


#1

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

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

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

#2

The below algorithm iteratively builds the tree by using a stack and a map to identify a value’s position in inorder traversal.

type Stack []*TreeNode		
func (s *Stack) Push(n *TreeNode) {
    *s = append(*s, n)
}
func (s *Stack) Pop() (n *TreeNode) {
    x := s.Len() - 1
    n = (*s)[x]
    *s = (*s)[:x]
    return
}
func (s *Stack) Len() int {
    return len(*s)
}
func (s *Stack) Peek() *TreeNode {
    x := s.Len() - 1
    return (*s)[x]
}
func buildTree(preorder []int, inorder []int) *TreeNode {
    if len(preorder)==0 || len(inorder)==0{ return nil}
    inOrderMap := make(map[int]int)
    for i, v := range inorder{
        inOrderMap[v] = i
    }
    stack := Stack{}
    root := &TreeNode{Val: preorder[0]}
    stack.Push(root)
    for i:=1;i<len(preorder);i++{
        val := preorder[i]
        node := &TreeNode{Val : val}
        if inOrderMap[val] < inOrderMap[stack.Peek().Val]{
            stack.Peek().Left = node
        } else {
           var parent *TreeNode
            for stack.Len()!=0 && inOrderMap[val] >inOrderMap[stack.Peek().Val]{
                parent = stack.Pop()
            }
            
            parent.Right = node
        }
        stack.Push(node)
    }
    
    return root
}

#3

A recursive approach in Java.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        Map<Integer, Integer> im = new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            im.put(inorder[i], i);
        }      
        return helper(0, 0, inorder.length-1, preorder, inorder, im);
    } 
    
    public TreeNode helper(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder, Map<Integer, Integer> im){
        if(preStart > preorder.length-1 || inStart>inEnd){return null;}
        TreeNode node = new TreeNode(preorder[preStart]);
        int inIndex = im.get(preorder[preStart]);
        node.left = helper(preStart+1, inStart, inIndex-1, preorder, inorder, im);
        node.right = helper(preStart+inIndex-inStart+1, inIndex+1, inEnd, preorder, inorder, im);
        return node;
    }
}