面试题 04.09. 二叉搜索树序列

https://leetcode-cn.com/problems/bst-sequences-lcci/

题目描述

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



示例：
给定如下二叉树

        2
       / \
      1   3
返回：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bst-sequences-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

TODO

复杂度分析

• 时间复杂度：$O()$。

• 空间复杂度：$O()$。

代码

JavaScript Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var BSTSequences = function (root) {
    var res = dfs(root);
    return res;

    // ****************************

    function dfs(node) {
        if (!node) return [[]];
        if (!node.left && !node.right) return [[node.val]];

        // 左子树所有可能的序列
        var left = dfs(node.left);
        // 右子树所有可能的序列
        var right = dfs(node.right);
        // 组合
        var res = [];

        for (let l of left) {
            for (let r of right) {
                // 左右子树的组合不止两种，具体看 merge 函数的注释
                var merged = merge(l, r);
                // 父节点总是在开头
                res.push(...merged.map(el => [node.val, ...el]));
            }
        }
        return res;
    }

    /**
     * 返回 arr1 和 arr2 的所有排列组合
     * @param arr1
     * @param arr2
     */
    function merge(arr1, arr2) {
        if (arr1.length == 0 && arr2.length == 0) {
            return [];
        }
        if (arr1.length == 0) return [arr2];
        if (arr2.length == 0) return [arr1];

        var res1 = [];
        if (arr1.length > 0) {
            // 设左子树的根节点为 p，右子树的根节点为 q
            // 插入 p 后，接下来可以插入 p 的子节点或者 q
            var merged = merge(arr1.slice(1), arr2);
            res1 = merged.map(sub => [arr1[0], ...sub]);
        }
        var res2 = [];
        if (arr2.length > 0) {
            // 设左子树的根节点为 p，右子树的根节点为 q
            // 插入 q 后，接下来可以插入 q 的子节点或者 p
            var merged = merge(arr1, arr2.slice(1));
            res2 = merged.map(sub => [arr2[0], ...sub]);
        }
        return [...res1, ...res2];
    }
};