LeetCode //C - 105. Construct Binary Tree from Preorder and Inorder Traversal-Toy模板网

这篇具有很好参考价值的文章主要介绍了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:

LeetCode //C - 105. Construct Binary Tree from Preorder and Inorder Traversal,LeetCode,leetcode,c语言,算法

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:

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.

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:

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.
Recursive Steps:文章来源地址https://www.toymoban.com/news/detail-701299.html

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.

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);
}

到了这里，关于LeetCode //C - 105. Construct Binary Tree from Preorder and Inorder Traversal的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！