二叉树 - 面试题 04.09. 二叉搜索树序列 - 《数据结构与算法》

题目
思路分析

题目

题目来源：力扣（LeetCode）

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

示例：
给定如下二叉树

    2<br />       / \<br />      1   3<br />返回：

[
[2,1,3],
[2,3,1]
]

思路分析

本题解参考自原书题解。

本题的难点在于二叉搜索树可以对应多个序列，因此从一些基本情况来枚举看看情况是比较好的思路。

首先从最简单的示例看看：

    2<br />       / \<br />      1   3<br />返回

[
[2,1,3],
[2,3,1]
]
由于是从数组中从左到右插入元素到二叉搜索树中，因此每个元素在已存在的二叉搜索树中的插入位置都是确定的。

可得结论：

数组的第一个元素，必定对应于二叉搜索树的树根。
一个节点对应的子节点在序列上必定在父节点元素之后，如上图子节点1、3在输出的序列中必定在父节点2之后。
猜想：各个序列的差异主要是子树的插入顺序不同，例如此例子可以对应先插左子树后插右子树，或者是先插右子树再插左子树。
得出基本结论后继续看看复杂一些的例子：

    2<br />       / \<br />      1   4<br />         /<br />        3

[
[2,1,4,3],
[2,4,1,3],
[2,4,3,1]
]
从本例来看，各个序列的差异主要是子树的插入顺序不同这一猜想不正确。插入的顺序可能是先插部分左子树节点，再插部分右子树节点。
并且插入的顺序始终不会违反结论2，节点3在序列中的位置必定在父节点4之后，因此可以说明序列中子树节点的相对顺序是可以确定的。

因此我们将子树中的节点看做单个序列，如上例中左边的序列为{2},右边的序列为{4,3}，将两个序列按照相对顺序进行混合：

[
[1,4,3],
[4,1,3],
[4,3,1]
]
如果此时再在各个序列中加上父节点生成的前缀2，恰好对应了答案。

因此只需递归地找到每个节点对应生成的序列，再在父节点进行混合，即可得到答案。

自上而下广度优先搜索

// javascript
let ans;
var BSTSequences = function(root) {
    ans = [];
    let path = [];
    // 如果 root = null 返回 [[]]
    if (root === null) {
        ans.push(path);
        return ans;
    }
    let queue = [root];
    // 开始进行回溯
    bfs(queue, path);
    return ans;
};
/**
 * 回溯法 + 广度优先遍历.
 */
var bfs = function(queue, path) {
    // 终止条件：queue 为空说明已经遍历完，存放结果，直接返回
    if (queue.length === 0) {
        ans.push(path.slice()); // ⚠️ 必须用 slice
        return;
    }
    let len = queue.length;
    // 对 queue 进行循环，对「将当前 cur 节点从 queue 中取出并将其左右子
    // 节点加入 queue，再将 cur.val 加入到 path 末尾」的情况进行回溯
    while (len > 0) {
        let cur = queue.shift();
        path.push(cur.val);
        // 将左右子节点加入队列
        if (cur.left != null) queue.push(cur.left);
        if (cur.right != null) queue.push(cur.right);
        bfs(queue, path);
        // 恢复 path 和 queue，进行回溯（因为是引用数据类型，递归时作为形参会被改变）
        path.pop();
        if (cur.left != null) queue.pop();
        if (cur.right != null) queue.pop();
        queue.push(cur);     
        len--;
    }
}

自下而上深度优先搜索+编织法

// javascript
var BSTSequences = function(root) { 
    let result = [];
    if (root === null) {
        result.push([]);
        return result;
    }
    let prefix = [root.val];
    // 对左右子树递归
    let leftSeq = BSTSequences(root.left);
    let rightSeq = BSTSequences(root.right);
    // 从每个链表的左右两端交替计算
    for (let left of leftSeq) {
        for (let right of rightSeq) {
            let weaved = [];
            weaveLists(left, right, weaved, prefix);
            result = result.concat(weaved); // 注意 ⚠️
        }
    }
    return result;
}
// 以所有可能的方式对链表同时交替计算。该算法从一个链表的头部移除元素，递归，并对另一个链表做相同的操作
var weaveLists = function(first, second, results, prefix) {
    // 一个链表已空。将剩余部分加入到(复制后的)prefix 中并存储结果
    if (first.length === 0 || second.length === 0) {
        let result = prefix.slice();
        result = result.concat(first, second);
        results.push(result);
        return;
    }
    // 将 first 的头部加入到 prefix 后进行递归。移除头部元素会破坏 first，
    // 因此我们需要在后续操作时将元素放回
    let headFirst = first.shift();
    prefix.push(headFirst);
    weaveLists(first, second, results, prefix);
    prefix.pop();
    first.unshift(headFirst);
    // 对 second 做相同操作，破坏链表并恢复
    let headSecond = second.shift();
    prefix.push(headSecond);
    weaveLists(first, second, results, prefix);
    prefix.pop();
    second.unshift(headSecond);
}

参考： https://blog.csdn.net/weixin_45561634/article/details/119721261 https://leetcode-cn.com/problems/bst-sequences-lcci/solution/ru-he-tong-guo-li-zi-de-chu-jie-by-user5707f/ https://leetcode-cn.com/problems/bst-sequences-lcci/solution/mei-yi-ge-jie-dian-du-bi-xu-pai-zai-ta-d-n679/