(相关资料图)

题目：

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

给定一个由不同节点组成的二叉搜索树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]]

代码实现：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    private List> ans;    public List> BSTSequences(TreeNode root) {        ans = new ArrayList<>();        List path = new ArrayList<>();        // 如果 root==null 返回 [[]]        if (root == null) {            ans.add(path);            return ans;        }        List queue = new LinkedList<>();        queue.add(root);        // 开始进行回溯        bfs(queue, path);        return ans;    }    /**     * 回溯法+广度优先遍历.     */    private void bfs(List queue, List path) {        // queue 为空说明遍历完了，可以返回了        if (queue.isEmpty()) {            ans.add(new ArrayList<>(path));            return;        }        // 将 queue 拷贝一份，用于稍后回溯        List copy = new ArrayList<>(queue);        // 对 queue 进行循环，每循环考虑 “是否 「将当前 cur 节点从 queue 中取出并将其左右子        // 节点加入 queue ，然后将 cur.val 加入到 path 末尾」 ” 的情况进行回溯        for (int i = 0; i < queue.size(); i++) {            TreeNode cur = queue.get(i);            path.add(cur.val);            queue.remove(i);            // 将左右子节点加入队列            if (cur.left != null) queue.add(cur.left);            if (cur.right != null) queue.add(cur.right);            bfs(queue, path);            // 恢复 path 和 queue ，进行回溯            path.remove(path.size() - 1);            queue = new ArrayList<>(copy);        }    }}