1、思路

• 遍历数组，将元素逐个插入树中生成二叉搜索树的过程，可以反过来看成是遍历二叉搜索树的过程。每个节点只能前往它的左右子节点，不能直接到达孙子节点，且一棵树的根节点总是先于它的左右子树被插入到树中；

• 用一个双端队列deque来存储这次可以插入的候选节点，当队列中没有候选节点时，视为一种方案，存入结果数组中；

• 注意从队首取出，从队尾插入。

2、代码

class Solution {
private:
    vector<vector<int>> res;
    vector<int> tmp;

public:
    void dfs(deque<TreeNode*> dq)
    {
        if (dq.empty())
        {
            res.push_back(tmp);     //得到一种合法序列
            return;
        }

        int size = dq.size();
        while (size -- )            //二叉树的层序遍历
        {
            TreeNode* node = dq.front();
            dq.pop_front();

            tmp.push_back(node->val);

            if (node->left) dq.push_back(node->left);   //左右子树入队
            if (node->right) dq.push_back(node->right);

            dfs(dq);

            if (node->right) dq.pop_back();             //左右子树出队
            if (node->left) dq.pop_back();

            dq.push_back(node);
            tmp.pop_back();
        }
    }

    vector<vector<int>> BSTSequences(TreeNode* root) {
        if (root == nullptr) return {{}};

        deque<TreeNode*> dq;
        dq.push_back(root);
        dfs(dq);

        return res;
    }
};