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

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

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

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：

Postorder Traversal Insight:

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

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:

Start by identifying the root of the tree using the last element in the postorder list.
Search for this root in the inorder list to determine the boundary between the left and right subtrees.
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.

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

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

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