二叉树搜索序列（回溯）

        最近不知道干啥事，好像好多事要干，又好像啥事没有..我的心情be like

         然后我就打开力扣开始看题，按顺序刷题，就看到了这个题目：

         刚一看到，感觉简简单单小回溯，轻松拿捏

         再一看难度：困难，感觉不妙...再仔细一看，好像没有那么简单

         于是我想了一整堂课，终于有了一丢丢思路，然后就写了下来。主要是通过bfs和回溯算法联合使用解决。

 二、解题思路

        1、看示例、了解题意

        题目中说，从左向右遍历一个数组就插入数据就可以生成二叉搜索树。然后给了一个[2,1,3]的实例，如图可以看到它是一层一层插入的。也就是说[2,1,3]和[2,3,1]的差距就在于左右节点插入的顺序不同。因此我们很容易就看出，只要我们通过bfs的方法遍历每一层，然后在每一层通过回溯的方法先插入左节点，得到结果后回溯回来，再插入右节点，就可以完成操作了。

         2、确定数据结构和大致框架

        有了大概思路之后，我们就需要确定需要使用什么样的数据结构和什么样的框架了。

        首先，题目需要返回的类型是List>，因此我们需要定义一个最终返回结果ans，类型为List>。然后bfs必不可少的就是队列了，但是我们不选择Queue，因为我们需要进行回溯操作，需要删除指定节点，因此采用List较好。其次，ans保存的是所有可能的路径，因此我们还需要一个List类型的变量储存单次的路径。

        确定了数据结构，我们需要大概的框架，如下：

class Solution {
    // 定义全局的变量，也是函数返回值
    List> ans = new ArrayList<>();
    public List> BSTSequences(TreeNode root) {
        // 定义队列（存的是节点）
        List queue = new LinkedList<>();
        //定义单次路径
        List path = new ArrayList<>();
        // 判空处理
        if(root == null){
            ans.add(new ArrayList<>(path));
            return ans;
        }
        // bfs老套路，先把头结点放进去，不然循环进不去
        queue.add(root);
        bfs(queue,path);
        // 调用后返回结果
        return ans;
    }
    public void bfs(List queue,List path){
        
    }
}

        咋样，有没有清晰一点？

        有？

        难点还在后面

         主函数大概写好了，那么关键的bfs函数确实是个难点。

        那么我们再写下回溯的框架吧

        

    public void bfs(List queue,List path){
        if(queue.isEmpty()){
            ans.add(new ArrayList<>(path));
            return;
        }
        int size = queue.size();
        // 保存当前队列
        for(int i = 0; i < size; i++){
            // 加节点等一系列操作
            // 再次调用
            bfs(queue,path);
            //当执行到这一步说明一条路径走完了，需要删除当点节点重新选取节点再来一遍
            path.remove(path.size() - 1);
            //恢复队列
        }
 
        
    }

               大致框架是这个：

                当队列为空的时候，说明节点都已经加入到path里面了，因此path里存的已经是一个完整的路径了，可以加入到ans里去，然后别忘记返回。

                之后循环队列，取出当前队列头部的节点，把它的值放入path中，代表了选择了这个节点，然后再将选择的节点的左右节点加入队列（bfs套路）。放入之后，再次调用bfs循环操作。之后指定到下一步的时候已经需要恢复现场了。

                这里注意！！恢复现场需要恢复两个东西，一个是队列queue、一个是路径path。path比较容易，只需要删除最新加入的那个节点的值就可以了。但是queue稍微麻烦点，不可以通过queue.remove(queue.size() - 1);这种粗暴的方式实现。原因是队列有时候执行到这一步的时候已经是空队列了，执行这一步会报下标越界的错误。

                正确的做法是在进入循环之前，先保存一次队列，然后恢复现场的时候直接让队列等于保存的队列就可以了。总的代码如下：

                

class Solution {
    List> ans = new ArrayList<>();
    public List> BSTSequences(TreeNode root) {
        List queue = new LinkedList<>();
        List path = new ArrayList<>();
        if(root == null){
            ans.add(new ArrayList<>(path));
            return ans;
        }
        queue.add(root);
        bfs(queue,path);
        return ans;
    }
    public void bfs(List queue,List path){
        if(queue.isEmpty()){
            ans.add(new ArrayList<>(path));
            return;
        }
        int size = queue.size();
        List copy = new ArrayList<>(queue);
        for(int i = 0; i < size; i++){
            TreeNode head = queue.get(i);
            path.add(head.val);
            queue.remove(i);
            if(head.left != null)
                queue.add(head.left);
            if(head.right != null)
                queue.add(head.right);
            bfs(queue,path);
            path.remove(path.size() - 1);
            queue = new ArrayList<>(copy);
            //queue.remove(queue.size() - 1);
        }
 
        
    }
}

        最后运行的结果如下：

         好像不是特别好，于是我又在题解里找了份比较好的回溯。写的相当的nice啊

         代码贴下去了：

class Solution {
    private LinkedList path = new LinkedList<>();
    private List> result = new LinkedList<>();
    public List> BSTSequences(TreeNode root) {
        Deque dq = new LinkedList<>();
        if (root != null) {
            dq.offer(root);
        }
        dfs(dq);
        return result;
    }
    public void dfs(Deque dq) {
        if (dq.isEmpty()) {
            result.add(new ArrayList(path));
            return;
        }
        int size = dq.size();
        while(size > 0) {
            TreeNode cur = dq.pollFirst();
            path.add(cur.val);
            int children = 0;
            if (cur.left != null) {
                children++;
                dq.offerLast(cur.left);
            }
            if (cur.right != null) {
                children++;
                dq.offerLast(cur.right);
            }
            dfs(dq);
            while (children > 0) {
                dq.pollLast();
                children--;
            }
            dq.offerLast(cur);
            path.removeLast();
            size--;
        }
    }
}

三 、尾声

        最近题写的不多，题解就更少了。但是我想把为数不多的题解写的有趣一些，因此加了一些表情包，希望大家喜欢。