Construct BST from Post Order Traversal

Given the sequence of keys visited by a postorder traversal of a binary search tree, reconstruct the tree.

For example, given the sequence 2, 4, 3, 8, 7, 5, you should construct the following tree:

    5
   / \
  3   7
 / \   \
2   4   8

Example:

Input:  postorder = {2,4,3,8,7,5}
Output: [5,3,7,2,4,null,8]

Approach

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int findLastSmaller(vector<int&nodes,
                    int firstint lastint cut)
{

    if (last < first || nodes[first] > cut)
        return first - 1;

    int low = firsthigh = lastmid;

    while (low < high && nodes[high] > cut)
    {

        mid = low + (high - low + 1) / 2;

        if (nodes[mid] > cut)
        {

            high = mid - 1;
        }
        else
        {
            low = mid;
        }
    }

    return high;
}
TreeNode *recursiveFromPostOrder(vector<int&nodes,
                                 int leftIndexint rightIndex)
{

    if (rightIndex < leftIndex)
        return NULL;

    if (rightIndex == leftIndex)
        return new TreeNode(nodes[leftIndex]);

    int rootval = nodes[rightIndex];

    TreeNode *root = new TreeNode(rootval);

    int leftLast = findLastSmaller(nodes,
                                   leftIndex,
                                   rightIndex - 1rootval);

    root->left = recursiveFromPostOrder(nodesleftIndex,
                                        leftLast);

    root->right = recursiveFromPostOrder(nodesleftLast + 1,
                                         rightIndex - 1);
    return root;
}
TreeNode *fromPostOrder(vector<int&nodes)
{

    if (nodes.size() == 0)
        return NULL;
    return recursiveFromPostOrder(nodes0nodes.size() - 1);
}

void printTree(TreeNode *root)
{
    queue<TreeNode *> q;
    q.push(root);
    vector<stringvec;
    while (!q.empty())
    {
        root = q.front();
        q.pop();
        if (root == NULL)
            vec.push_back("null");
        else
            vec.push_back(to_string(root->data));
        if (root != NULL)
        {
            q.push(root->left);
            q.push(root->right);
        }
    }
    int j = vec.size() - 1;
    while (j > 0 && vec[j] == "null")
        j--;
    vec.resize(j);
    cout << "[";
    for (int i = 0i < ji++)
        cout << vec[i] << ",";
    cout << vec[j];
    cout << "]";
}
int main()
{
    vector<intpostorder = {243875};

    TreeNode *root = fromPostOrder(postorder);

    printTree(root);

    return 0;
}


No comments:

Post a Comment