C 8ms (100%), Simple 8-Line Recursive, Explained
Solution\nc\nstruct TreeNode* buildTree(int* inorder, int inlen, int* postorder, int postlen){\n    if(inlen == 0) return NULL;\n\t\n    // Last elem of postord
# **Solution**\n```c\nstruct TreeNode* buildTree(int* inorder, int inlen, int* postorder, int postlen){\n    if(inlen == 0) return NULL;\n\t\n    // Last elem of postorder must be (sub)tree\'s root\n    struct TreeNode* curr = malloc(sizeof(struct TreeNode));\n    curr->val = postorder[postlen-1];\n\t\n    // Find partition index\n    int mid = 0;\n    while(inorder[mid]!=curr->val) ++mid;\n\t\n    curr->left = buildTree(&inorder[0], mid, &postorder[0], mid);\n    curr->right = buildTree(&inorder[mid+1], inlen-mid-1, &postorder[mid], inlen-mid-1);\n    return curr;\n}\n```\n\n# **Explanation**\nThere are 2 properties that we can use to arrive at our solution.\nA. In the `postorder` array, the last element **must** be the `root` node.\nB. In the `inorder` array, all the elements *left* of `root` must belong to `root`s left tree. Similarly, all the elements *right* of `root` must belong to `root`\'s right tree.\n\n## **Divide & Conquer**\n*Initialisation*\n1. For any input, ``postorder[postlen-1]`` **must** be the root of the (sub)tree. I named `root` as `curr` for distinction between the tree root & subtree \'root\'.\n2. So, for every function call a `TreeNode` named `curr` with value `postorder[postlen-1]` is made.\n3. Find the index, `mid`, where `curr` appears in `inorder`. With the index, we can determine `curr`\'s left and right elements in `postorder` and `inorder` respectively.\n\n*Division*\nBy repeatedly partitioning our input arrays around each function call\'s subtree root, `curr`, we will narrow down the array until we get a base case where the length of the input array is zero. We will return NULL in that case. This return value will later be assigned to the parent\'s left/right node as explained in \'conquer\'.\n\nNote: In effect, each function call divides the tree into smaller subtrees. `curr` each subtree\'s root.\n\n4. Recursively call the function on the left and right subarrays (representing the subtrees).\nThe array length of the left subtree must be equal to `mid`, the partition index.\nThe array length of the right subtree must be equal to `inlen-mid-1`. (You can verify using the sample testcase provided!)\n\nTranslated into code:\n```c\nbuildTree(???, mid, ???, mid);\n```\n5. We need to input arrays for `???`. We *could* copy the values into a new array, but since this is C, we can provide the subtree array\'s starting element *memory address* instead to save space.\nLength is not a concern and will resolve itself since we input the supposed length of the subtree arrays already.\nDetermining the mem addess is straightforward for the LEFT recursion call.\nBut for RIGHT, due to the ordering of elements, `inorder` should start at `mid+1`, not `mid`.\nYou can verify this using the sample testcase provided in the qn.\n\nTranslated into code:\n```c\nbuildTree(&inorder[0], mid, &postorder[0], mid); // LEFT\nbuildTree(&inorder[mid+1], mid, &postorder[mid], mid); // RIGHT\n```\n\n*Conquer*\n6. The function will either return `NULL` or the \'root\' node of a certain subtree.\n7. Build the tree by assigning `curr`\'s left and right to the returned value of the recursion calls.\n8. Profit\n\nHope this explanation and solution helps! Cheers\n
['Recursion', 'C', 'Binary Tree']