LeetCode //C - 105. Construct Binary Tree from Preorder and Inorder Traversal

105. Construct Binary Tree from Preorder and Inorder Traversal

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

Example 1:

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

Example 2:

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

Constraints:

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

From: LeetCode
Link: 105. Construct Binary Tree from Preorder and Inorder Traversal

---

Solution:

Ideas：

The idea behind the solution is based on the following key observations regarding the properties of the preorder and inorder traversals of a binary tree:

1. Preorder Traversal (Root, Left, Right):

• The first element in the preorder traversal gives the root of the tree/subtree.
• Subsequent elements can be divided into two groups based on this root: the left subtree nodes and the right subtree nodes.

2. Inorder Traversal (Left, Root, Right):

• Given a root, you can determine the number of nodes in the left and right subtrees by finding the root’s position in the inorder traversal.
• All elements to the left of the root in the inorder traversal belong to the left subtree. Similarly, all elements to the right of the root belong to the right subtree.

Using these properties, the algorithm constructs the binary tree in the following manner:

1. Base Case: If the provided subsections of the preorder or inorder lists are empty (i.e., start index is greater than the end index), return NULL. This means there’s no tree to be constructed for that particular subsection.

2. Recursive Steps:

• Take the first element from the preorder list as the current root of the tree/subtree.
• Find the position of this root in the inorder list. This will effectively split the inorder list into two parts: nodes belonging to the left subtree and nodes belonging to the right subtree.
• Calculate the lengths of these left and right subtrees.
• Use these lengths to determine the sections of the preorder list that correspond to the left and right subtrees.
• Make recursive calls to construct the left and right subtrees using the subsections of the preorder and inorder lists corresponding to the left and right subtrees, respectively.
• Connect the constructed left and right subtrees to the current root.

3. Return the constructed tree.

Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int indexOf(int* arr, int start, int end, int value) {
    for (int i = start; i <= end; i++) {
        if (arr[i] == value) {
            return i;
        }
    }
    return -1;
}

struct TreeNode* helper(int* preorder, int preorderStart, int preorderEnd, 
                        int* inorder, int inorderStart, int inorderEnd) {
    if (preorderStart > preorderEnd || inorderStart > inorderEnd) {
        return NULL;
    }
    
    // Create the root node with the first value of the preorder list
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = preorder[preorderStart];
    
    // Get the position of root in inorder
    int rootIndex = indexOf(inorder, inorderStart, inorderEnd, root->val);
    
    // Calculate the length of the left and right subtrees
    int leftTreeLength = rootIndex - inorderStart;
    int rightTreeLength = inorderEnd - rootIndex;
    
    // Construct left and right subtrees
    root->left = helper(preorder, preorderStart + 1, preorderStart + leftTreeLength, 
                        inorder, inorderStart, rootIndex - 1);
    
    root->right = helper(preorder, preorderStart + leftTreeLength + 1, preorderEnd, 
                         inorder, rootIndex + 1, inorderEnd);
    
    return root;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    return helper(preorder, 0, preorderSize - 1, inorder, 0, inorderSize - 1);
}
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
44
45
46
47