(相關資料圖)

題目：

從左向右遍歷一個數組，通過不斷將其中的元素插入樹中可以逐步地生成一棵二叉搜索樹。

給定一個由不同節點組成的二叉搜索樹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);        }    }}