//
// Created by 罗炳国 on 2023/7/14.
//

#ifndef PFJ_CODE04_BSTFROMPREORDER_H
#define PFJ_CODE04_BSTFROMPREORDER_H

#include "commonHeader.h"

/*
 * 给定一个整数数组，它表示BST(即 二叉搜索树 )的 先序遍历 ，构造树并返回其根。

保证 对于给定的测试用例，总是有可能找到具有给定需求的二叉搜索树。

二叉搜索树 是一棵二叉树，其中每个节点，Node.left的任何后代的值 严格小于 Node.val,Node.right的任何后代的值 严格大于 Node.val。

二叉树的 前序遍历 首先显示节点的值，然后遍历Node.left，最后遍历Node.right。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

class code04_bstFromPreorder {
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        int N = preorder.size();

        for (int i = 0; i < N; i++) {
            help.push_back(-1);
        }
        get_right_bigger(preorder, help);
        TreeNode *head;
        head = generate_tree(preorder, 0, N - 1);
        return head;
    }

    TreeNode *generate_tree(vector<int>& preorder, int l, int r) {
        if (l > r)
            return nullptr;
        int firstBig = help[l]; // 索引下标

        TreeNode *head = new TreeNode;
        head->val = preorder[l];
        head->left = firstBig == -1 ? generate_tree(preorder, l + 1, r) :
                generate_tree(preorder, l + 1, firstBig - 1);
        head->right = firstBig == -1 ? nullptr : generate_tree(preorder, firstBig, r);
        return head;
    }

    void get_right_bigger(vector<int>& preorder, vector<int> &ans) {
        int N = preorder.size();
        stack<int> st;
        for (int i = 0; i < N; i++) {
            while (!st.empty() && preorder[st.top()] < preorder[i]) {
                ans[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        while (!st.empty()) {
            ans[st.top()] = -1;
            st.pop();
        }
    }
private:
    vector<int> help;
};

#endif //PFJ_CODE04_BSTFROMPREORDER_H