Leetcode discuss: 889. Construct Binary Tree from Preorder and Postorder Traversal

 Here is the link. 

C# find left subtree by comparing two hashset

August 26, 2020

889. Construct Binary Tree from Preorder and Postorder Traversal

Introduction
I like to review my practice in 2018. The idea is to find left subtree's end position using two hashset comparison. The time complexity is not optimal, and it slows down the time complexity to O(n*n).
Case study
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]
The prerorder traversal [1, 2, 4, 5, 3, 6, 7], so first node is root node, and left subtree starts from index = 1 if there is one, 2 should be left subtree root value, and it's position is index = 2, last node in post order traversal. [4,5,2] is left subtree in post order.

It is better to find the left subtree's root in post order list using a hashmap with O(1) time complexity.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode ConstructFromPrePost(int[] pre, int[] post)
        {
            if (pre == null || post == null)
                return null;
            if (pre.Length != post.Length)
                return null;

            var length = pre.Length;

            return constructTree(pre, 0, length, post, 0);
        }

        /// <summary>
        /// based on the tree has distinct value for each node, left subtree can be determined by 
        /// comparison pre and post array subset. 
        /// </summary>
        /// <param name="pre"></param>
        /// <param name="start1"></param>
        /// <param name="end1"></param>
        /// <param name="post"></param>
        /// <param name="start2"></param>
        /// <param name="end2"></param>
        /// <returns></returns>
        private static TreeNode constructTree(int[] pre, int start1, int length, int[] post, int start2)
        {
            if (start1 >= pre.Length || length == 0)  // caught by online judge
                return null;

            if (length == 1)
            {
                return new TreeNode(pre[start1]);
            }

            var root = new TreeNode(pre[start1]);
            
            var setPre = new HashSet<int>();
            var setPost = new HashSet<int>();

            // Find left subtree
            int index = 0;
            while (index < length)
            {
                setPre.Add(pre[start1 + 1 + index]); // caught by online judge, + 1, skip the root
                setPost.Add(post[start2 + index]);
                if (setPre.IsSubsetOf(setPost) && setPost.IsSubsetOf(setPre))
                {
                    break;
                }

                index++;
            }

            var leftSubtreeLength  = index + 1;
            var rightSubtreeLength = length - leftSubtreeLength - 1;
 
            root.left  = constructTree(pre, start1 + 1,                     leftSubtreeLength,  post, start2);
            root.right = constructTree(pre, start1 + 1 + leftSubtreeLength, rightSubtreeLength, post, start2 + leftSubtreeLength);

            return root; 
    }
}