Today I have done leetcode's February LeetCoding Challenge with cpp.

February LeetCoding Challenge 23

Description

Construct Binary Tree from Preorder and Postorder Traversal

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]

Constraints:

• 1 <= preorder.length <= 30
• 1 <= preorder[i] <= preorder.length
• All the values of preorder are unique.
• postorder.length == preorder.length
• 1 <= postorder[i] <= postorder.length
• All the values of postorder are unique.
• It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Solution

class Solution {
public:
  TreeNode* constructFromPrePost(
    vector<int>& preorder,
    vector<int>& postorder,
    int prebegin = -1,
    int preend = -1,
    int postbegin = -1,
    int postend = -1
  ) {
    if(prebegin == -1) {
      prebegin = 0;
      preend = preorder.size() - 1;
      postbegin = 0;
      postend = preorder.size() - 1;
    }
    if(prebegin > preend) return nullptr;
    TreeNode *root = new TreeNode(preorder[prebegin]);
    if(prebegin == preend) return root;
    int pivot = -1;
    for(int i = postbegin; i <= postend && pivot == -1; ++i) {
      if(postorder[i] == preorder[prebegin + 1]) {
        int offset = i - postbegin;
        root->left = constructFromPrePost(preorder, postorder, prebegin + 1, prebegin + 1 + offset, postbegin, postbegin + offset);
        pivot = offset;
      }
    }
    if(prebegin + 1 + pivot == preend) return root;
    root->right = constructFromPrePost(preorder, postorder, prebegin + 1 + pivot + 1, preend, postbegin + pivot + 1, postend - 1);
    return root;
  }
};

// Accepted
// 306/306 cases passed (0 ms)
// Your runtime beats 100 % of cpp submissions
// Your memory usage beats 56.32 % of cpp submissions (28.2 MB)