Leetcode discuss: 105 Construct Binary Tree from Preorder and Inorder Traversal

 Here is the link. 

August 28, 2020
Introduction
It is important to write a solution using optimal time complexity. Put inorder traversal list into a hashmap since all nodes have distinct value, so it takes O(1) time to find root node's index in inorder traversal list.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    /// <summary>
        /// August 28, 2020
        /// The idea is to put inorder traversal list into a hashmap, so lookup can be O(1) time complexity;
        /// Just apply recursive function to solve the problem, each time the root node can be found 
        /// from the first node in preorder traversal list. 
        /// </summary>
        /// <param name="preorder"></param>
        /// <param name="inorder"></param>
        /// <returns></returns>
        public TreeNode BuildTree(int[] preorder, int[] inorder)
        {
            if (preorder == null || inorder == null || preorder.Length != inorder.Length ||
               preorder.Length == 0)
            {
                return null;
            }

            var map = new Dictionary<int, int>();
            var inLength = inorder.Length;
            for (int i = 0; i < inLength; i++)
            {
                map.Add(inorder[i], i);
            }

            return runHelper(preorder, 0, preorder.Length - 1, inorder, 0, inorder.Length - 1, map);
        }

        /// <summary>
        /// Recursive function, each step one node is solved in binary tree 
        /// </summary>
        /// <param name="preorder"></param>
        /// <param name="preStart"></param>
        /// <param name="preEnd"></param>
        /// <param name="inorder"></param>
        /// <param name="inStart"></param>
        /// <param name="inEnd"></param>
        /// <param name="map"></param>
        /// <returns></returns>
        private TreeNode runHelper(int[] preorder, int preStart, int preEnd, 
            int[] inorder, int inStart, int inEnd, Dictionary<int, int> map)
        {
            if (preStart > preEnd)
            {
                return null;
            }

            var rootValue = preorder[preStart];
            var root = new TreeNode(rootValue);

            var rootIndex = map[rootValue];
            // calculate left subtree's length using inorder list
            var leftSubTree  = rootIndex - inStart;
            var rightSubTree = inEnd - rootIndex; 

            root.left = runHelper(preorder, preStart + 1, preStart + leftSubTree, 
                                  inorder,  inStart,      inStart + leftSubTree - 1, map);
            root.right = runHelper(preorder, preStart + leftSubTree + 1, preEnd,
                                  inorder,   rootIndex + 1, inEnd, map);
            return root; 
        }
}