一、题目

从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。

给定一个由不同节点组成的二叉搜索树 root，输出所有可能生成此树的数组。

点击此处跳转题目。

示例 1:

输入: root = [2,1,3]
输出: [[2,1,3],[2,3,1]]
解释: 数组 [2,1,3]、[2,3,1] 均可以通过从左向右遍历元素插入树中形成以下二叉搜索树

   2 / \ 1   3

示例 2:

输入: root = [4,1,null,null,3,2]
输出: [[4,1,3,2]]

提示：

二叉搜索树中的节点数在 [0, 1000] 的范围内
1 <= 节点值 <= 10^6
用例保证符合要求的数组数量不超过 5000

二、C# 题解

分析题目，第一个放入的只能是根结点，其次是其左右孩子。流程如下：

首先可以放入根结点：【2】
2 放入后，其左右孩子都可以放入：【1,4】
放入 1 时，后续可以放入：【5,4】；放入 4 时，后续可以放入：【1,6,7】
…

因此可以发现，这是一个逐步推进的过程，即数组中每次放入的结点只能是当前已放入结点的孩子，而不能越级。一旦越级，例如依次放入：【2,1,6】，会发现放入 6 时，6 将直接成为 2 的右孩子，将 4 这一层打破了。

在这里插入图片描述
使用 next 数组记录后续可以访问的结点，lst 数组记录每一个答案。递归回溯求解如下：

/*** Definition for a binary tree node.* public class TreeNode {*     public int val;*     public TreeNode left;*     public TreeNode right;*     public TreeNode(int x) { val = x; }* }*/
public class Solution {public IList<IList<int>> BSTSequences(TreeNode root) {IList<IList<int>> ans = new List<IList<int>>();// 如果树为空，返回空if (root == null) { ans.Add(new List<int>()); return ans; }// BFS 遍历，将结果存储到 ans 中Partition(ans, new List<int>(), new List<TreeNode> { root });return ans;}// lst 存储每种情况的数组，next 存储下一个访问结点public void Partition(IList<IList<int>> ans, IList<int> lst, List<TreeNode> next) {// 遍历每个 next 结点for (int i = 0; i < next.Count; i++) {// 结点处理TreeNode node = next[i];                      // 取出该结点 nodelst.Add(node.val);                            // 将 node 值加入 lst 中next.Remove(node);                            // 访问完成后删除 node 记录if (node.left != null) next.Add(node.left);   // 左右孩子不为空，则将成为下一个访问节点if (node.right != null) next.Add(node.right);Partition(ans, lst, next); // 继续访问后续结点// 访问完成后，回到原始状态，为进入下一个 next 结点做准备next.Insert(i, node);    // 收回 node 结点next.Remove(node.left);  // 删除 node 左右孩子的记录next.Remove(node.right);lst.Remove(node.val);    // 取出 node 值}if (next.Count == 0) ans.Add(new List<int>(lst)); // next 为空，表示遍历完所有结点，此时将 lst 放入 ans 中// 注意需要拷贝 lst，否则加入的是引用}
}