Leetcode discuss: 106 Construct Binary Tree from Inorder and Postorder Traversal

Here is the link. 

C# practice to prepare FANG onsite 2020

August 1, 2020
106 Construct Binary Tree from Inorder and Postorder Traversal
Assume that all nodes have distince value, construct binary tree from inorder and postroder traversal.

Introduction

It is tough decision for me to work on system design, reading networking and operation system lecture notes. I did not have time to practice algorithm after phone screen. This is the first algorithm I wrote after break from July 20. I have two more weeks to practice algorithm.

Algorithm case study
Quick review, inorder traversal is left child, root and right child whereas post order traversal is left child, right child and root node.

Example:
[9, 3, 15, 20, 7] - inorder
[9, 15, 7, 20, 3] - postorder
It is easy to find root node by post order traversal. Last node of postorder traversal is the root node, the example tree is root node with value 3. Next go through inorder traversal hashmap, rootnode 3 has index value 1. So left subtree has subarray [9], right subtree has subarray [15, 20, 7] inorder traversal. Also left subtree's length is 1, right subree length is 3.

Next it is to work on post order traversal list. First part is left subtree, knowing start index and length; Next part is right subree and length of subtree.

Highlights of my practice

1. Work on test case given in the above, and then try to write simple code;
2. If the left subtree is empty, then the subarray's start and end index will have contraction: endIndex < startIndex;
3. Work on length of left subtree and right subtree;
4. Be patient. I came cross the time limit exceeded. So I started to test code using the above test case, and found two places to fix.
5. Trust the example test case is good enough to write bug-free code. Go through step by step.

/**
 * 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 {
    // [9, 3, 15, 20, 7] - inorder
    // [9, 15, 7, 20, 3] - postorder
    //
    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        if(inorder == null || postorder == null || inorder.Length != postorder.Length || inorder.Length == 0)
        {
            return null; 
        }
        
        // the idea is to find root node from post order, step 1;
        // use root node to look up inorder traversal, and then find root node, step 2;
        // Based on the above two steps, left subtree array is defined by start and end index, same as right subtree
        var map = new Dictionary<int, int>(); 
        for(int i = 0; i < inorder.Length; i++)
        {
            map.Add(inorder[i],i);
        }
        
        return runRecursiveSolution(inorder, 0, inorder.Length - 1, postorder, 0, postorder.Length - 1, map);        
    }
    
   // [9, 3, 15, 20, 7] - inorder
    // [9, 15, 7, 20, 3] - postorder
    // inorder
    // left subtree - [9]
    // right subtree [15, 20, 7]
    //
    // postorder
    // left subtree - knowing the length is 1
    // [9]
    // right subtree
    // [15, 7, 20]
    // how to express empty tree? 
    // how to express empty left/ right subtree using index?
    // define endIn < startIn or startPost < endPost - make it simple
    private TreeNode runRecursiveSolution(int[] inorder, int startIn, int endIn, int[] postorder, int startPost, int endPost, Dictionary<int, int> map)
    {
        // base case ?        
        if(startIn > endIn || startPost > endPost)
            return null;
        
        var rootValue = postorder[endPost];         
        var root = new TreeNode(rootValue);        
        
        var inorderIndex = map[rootValue]; // 1
        
        // left subtree - inorder list before root node
        var leftCount = inorderIndex - startIn;         
        
        var endPostNext = startPost + leftCount -1;
        
        // if left subtree is empty, then inorderIndex - 1 < startIn
        root.left = runRecursiveSolution(inorder, startIn, inorderIndex - 1, postorder, startPost, endPostNext, map);
        
        // right subtree - inorder list after root node
        var rightStart = endPostNext + 1;  // should be +1, not +2
        //var rightCount = endPostNext - startPost + 1; 
        var rightCount = endIn - inorderIndex; // calculate by inorder list 
        
        root.right = runRecursiveSolution(inorder, inorderIndex + 1, endIn,                                          
        postorder, rightStart, rightStart + rightCount - 1, map);        
        
        return root;               
    }
}