106. Construct Binary Tree from Inorder and Postorder Traversal

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

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.

🧠 Thuật Toán & Kỹ Thuật

Tree Traversal (Duyệt cây)
⏱️ Thời gian O(n)
💾 Không gian O(n)

💻 Lời Giải

C++ 0106-construct-binary-tree-from-inorder-and-postorder-traversal.cpp 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
private:
    vector<int> inorder, postorder;
    int curr;
    
public:
    TreeNode* build(int l, int r) {
        if (l > r) {
            return nullptr;
        }
        int i = 0;
        while (curr >= 0 and inorder[i] != postorder[curr]) {
            i++;
        }
        curr--;
        TreeNode *root = new TreeNode(inorder[i]);
        root->right = build(i + 1, r);
        root->left = build(l, i - 1);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->inorder = inorder;
        this->postorder = postorder;
        this->curr = inorder.size() - 1;
        return build(0, curr);
    }
};