LeetCode //C - 106. Construct Binary Tree from Inorder and Postorder Traversal

106. Construct Binary Tree from Inorder and Postorder Traversal

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
 

Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

Constraints:

• 1 <= inorder.length <= 3000
• postorder.length == inorder.length
• -3000 <= inorder[i], postorder[i] <= 3000
• inorder and postorder consist of unique values.
• Each value of postorder also appears in inorder.
• inorder is guaranteed to be the inorder traversal of the tree.
• postorder is guaranteed to be the postorder traversal of the tree.

From: LeetCode
Link: 106. Construct Binary Tree from Inorder and Postorder Traversal

---

Solution:

Ideas：

1. Postorder Traversal Insight:

• In a postorder traversal, the last element is always the root of the tree (or subtree).

2. Inorder Traversal Insight:

• In an inorder traversal, once you locate the root (from the postorder traversal), everything to the left of the root in the inorder list is the left subtree, and everything to the right is the right subtree.

Given these insights, here’s the step-by-step approach:

1. Start by identifying the root of the tree using the last element in the postorder list.
2. Search for this root in the inorder list to determine the boundary between the left and right subtrees.
3. Recursively apply the above steps for the left and right subtrees:

• For the left subtree: use the portion of the inorder list before the root and the corresponding elements from the postorder list.
• For the right subtree: use the portion of the inorder list after the root and the corresponding elements from the postorder list.

4. Stop the recursion when the start index is greater than the end index in the inorder list.

The function build is a recursive helper function that constructs the tree. It accepts the current boundaries (start and end indices) of the inorder list it should consider. It also accepts a pointer to the current index in the postorder list, which is decremented with each recursive call.

The function buildTree is the main function that initiates the tree construction. It starts the process by setting the postorder index to the last element and calling the build function.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* build(int* inorder, int inStart, int inEnd, 
                       int* postorder, int* postIndex) {
    // Base condition
    if (inStart > inEnd) return NULL;

    // Allocate memory for the new node
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    
    // The current postIndex is the value of the root for this subtree
    node->val = postorder[*postIndex];
    node->left = NULL;   // Initialize left child to NULL
    node->right = NULL;  // Initialize right child to NULL
    (*postIndex)--;

    // If there's no left or right children, return the node
    if (inStart == inEnd) return node;

    // Find the index of the current node in inorder to split left and right subtree
    int inIdx;
    for (inIdx = inStart; inIdx <= inEnd; inIdx++) {
        if (inorder[inIdx] == node->val) break;
    }

    // Recursively build the right and then the left subtree
    node->right = build(inorder, inIdx + 1, inEnd, postorder, postIndex);
    node->left = build(inorder, inStart, inIdx - 1, postorder, postIndex);

    return node;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
    // Start from the end of postorder (which represents the root of the tree)
    int postIndex = postorderSize - 1;
    return build(inorder, 0, inorderSize - 1, postorder, &postIndex);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43