题目

从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。

示例：

输入：[2,1,3]
即给定如下二叉树：
        2
       / \
      1   3
输出：
[
   [2,1,3],
   [2,3,1]
]

吐槽：出题的人在描述题目和给定示例的时候能不能说人话！！！

解释一下上面的示例，对于给定的这棵二叉树：

生成此二叉树的数组的第一个元素必须是根节点的值 2
- 原因：每次插入时，只能插入为当前已生成的二叉搜索树中的任一节点的子节点，而不能插入为某一节点的父节点。因此，如果数组的第一个元素不是 2，例如是 1，那么生成的二叉树的根节点的值就只能是 1 了，之后 2 就只能作为 1 的子孙节点的值了
数组的第二个元素可以是 1 or 3，哪个先插入二叉树无所谓，最终都能生成给定的这棵二叉树

因此，答案是：[[2,1,3],[2,3,1]]

解答 & 代码

再吐槽一下，给的示例也太不具代表性了！！！

再给一个更具代表性的例子：

输入：[5,3,8,1,4,null,9]
即给定如下二叉树：
         5
       /   \
      3     8
         / \     \
    1   4     9
输出：
[
    [5,3,8,1,4,9],[5,3,8,1,9,4],[5,3,8,4,9,1],[5,3,8,4,1,9],[5,3,8,9,1,4],
  [5,3,8,9,4,1],[5,3,1,4,8,9],[5,3,1,8,4,9],[5,3,1,8,9,4],[5,3,4,8,1,9],
  [5,3,4,8,9,1],[5,3,4,1,8,9],[5,8,3,9,1,4],[5,8,3,9,4,1],[5,8,3,1,4,9],
  [5,8,3,1,9,4],[5,8,3,4,9,1],[5,8,3,4,1,9],[5,8,9,3,1,4],[5,8,9,3,4,1]
]

插入原则：每次插入时，只能插入为当前已生成的二叉搜索树中的任一节点的子节点，而不能插入为某一节点的父节点。

对于上面给定的这棵二叉树：

生成此二叉树的数组的第一个元素必须是根节点的值 5（原因是插入原则的限制）
数组的第二个元素可以是 [3,8] 两个值中的任意一个，哪个先插入都能正确生成给定的二叉树
- 若数组开头为 [5,3] ，即第二步插入 3，则数组的第三个元素可以为 [8,1,4]
  - 若数组开头为 [5,3,8]，即第三步插入 8，则数组的第四个元素可以为 [1,4,9]
    - 若数组开头为 [5,3,8,1]，即第四步插入 1，则数组的第五个元素可以为 [4,9]
      - 若数组开头为 [5,3,8,1,4]，即第五步插入 4，则数组的第六个元素可以为 [9]
        
        第六步插入 9，数组为 [5,3,8,1,4,9]，插入结束
      - …
    - …
  - …
- 若数组开头为 [5,8] ，即第二步插入 8，则数组的第三个元素可以为 [3,9]
  - …

因此，算法流程如下：

使用一个数组 path 来记录当前已经插入的节点值，初始为空
使用一个双端队列(deque) nodeQ 来记录这一步可以插入的候选节点，初始时，如果 root 节点不为空，则先将 root 节点压入 nodeQ 中
使用一个二维数组 pathList 来存储所有可行的 path ，初始为空
将 nodeQ、path、pathList 传入递归函数 BSTTraverse：
- 递归结束条件：nodeQ 为空，说明这一步没有可以插入的节点，也就是插入全部完成，已经构建好给定的二叉树了，将当前的 path 插入 pathList，递归结束，return
- 用 size 记录当前 nodeQ 中的元素个数，即这一步可以插入的候选节点数
- 再 size 范围内循环，即遍历这一步所有可能插入的候选节点
  - 从 nodeQ 头部弹出一个节点，作为这一步插入的节点 cur
  - 将 cur 的值插入 path 尾部，说明当前在二叉树中插入了 cur 节点
  - 如果 cur 节点的左子树不为空，将左子树压入 nodeQ 的尾部，作为下一步插入的备选节点之一
  - 如果 cur 节点的右子树不为空，将右子树压入 nodeQ 的尾部，作为下一步插入的备选节点之一
  - 递归处理后续插入的步骤
  - 回溯：
    - cur 节点有几个非空的孩子节点，说明递归之前在 nodeQ 的尾部插入了几个节点，就让 nodeQ 的尾部重新弹出几个节点，以恢复原样
    - 将 cur 节点压入到 nodeQ 的尾部（循环 next loop，会将另一个候选节点作为当前插入的节点，之后的步骤还得插入 cur节点，因此要重新压入 nodeQ，只不过要插入到尾部）
    - 将 path 的最后一个元素弹出，恢复原样
递归结束，返回主函数，将 pathList 作为答案返回

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    void BSTTraverse(deque<TreeNode*>& nodeQ, vector<int>& path, vector<vector<int>>& pathList)
    {
        // 递归结束条件
        if(nodeQ.empty())
        {
            pathList.push_back(path);
            return;
        }

        // 循环，遍历这一步可以插入的所有候选节点
        int size = nodeQ.size();
        for(int i = 0; i < size; ++i)
        {
            // 取一个候选节点，作为这一步插入的节点
            TreeNode* cur = nodeQ.front();
            nodeQ.pop_front();
            // 将这个节点的值存储到 path
            path.push_back(cur->val);

            // 将当前插入节点的子节点插入 nodeQ 末尾，作为下一步可插入的候选节点列表中
            if(cur->left)
                nodeQ.push_back(cur->left);
            if(cur->right)
                nodeQ.push_back(cur->right);

            // 递归出序后续插入节点的步骤
            BSTTraverse(nodeQ, path, pathList);

            // 回溯
            // 将之前压入 nodeQ 末尾的当前节点的孩子节点重新弹出，使 nodeQ 恢复原样
            if(cur->left)
                nodeQ.pop_back();
            if(cur->right)
                nodeQ.pop_back();
            // 将 cur 重新压回 nodeQ，只不过是压倒尾部，而不是头部
            nodeQ.push_back(cur);
            // 将之前压入 path 尾部的当前节点弹出，以恢复原样
            path.pop_back();
        }
    }
public:
    vector<vector<int>> BSTSequences(TreeNode* root) {
        deque<TreeNode*> nodeQ;
        if(root)
            nodeQ.push_back(root);
        vector<int> path;
        vector<vector<int>> pathList;
        BSTTraverse(nodeQ, path, pathList);
        return pathList;
    }
};

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 92.38% 的用户
内存消耗：12.6 MB, 在所有 C++ 提交中击败了 90.32% 的用户

《程序员面试金典（第 6 版）》

[困难] 4.9 二叉搜索树序列

题目

解答 & 代码