☆打卡算法☆LeetCode 95、不同的二叉搜索树 II 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个整数n，生成并返回所有由n个节点构成的二叉搜索树。”

题目链接：

来源：力扣（LeetCode）

链接：95. 不同的二叉搜索树 II - 力扣（LeetCode） (leetcode-cn.com)

2、题目描述

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：
输入： n = 1
输出： [[1]]

二、解题

1、思路分析

这道题首先了解一下什么是二叉搜索树。

二叉搜索树是一种经典的数据结构，有两种情况，要么为空树，要么就是有以下特点的二叉树：

• 如果左子树不空，则左子树上所有节点的值都小于根节点的值
• 如果右子树不空，则右子树上所有节点的值都小于根节点的值
• 左右子树也分别为二叉排序树

二叉搜索树既有链表的快速插入与删除操作的特点，也有数组快速查找的优势，常用于文件系统和数据库系统的排序和检索操作。

回到这道题，要找所有的二叉搜索树，就要穷举所有可能性，考虑可以用递归来解题。

假设序列长度为n，根节点值为i，那么左子树的节点集合为[1…i-1]，右子树的节点集合为[i+1…n]，当前值的集合为[start,end]，那么就可以将序列分为[start,i-1]和[i-1,end]两部分。

递归调用两部分获得所有可能的左右自述节点，然后从左子树选一个节点，然后从右子树集合中选一个节点拼接到根节点后面，就得到了一颗搜索二叉树。

按照上面的思路找出所有的节点。

2、代码实现

代码参考：

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1, n);
    }

    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<TreeNode>();
        if (start > end) {
            allTrees.add(null);
            return allTrees;
        }

        // 枚举可行根节点
        for (int i = start; i <= end; i++) {
            // 获得所有可行的左子树集合
            List<TreeNode> leftTrees = generateTrees(start, i - 1);

            // 获得所有可行的右子树集合
            List<TreeNode> rightTrees = generateTrees(i + 1, end);

            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode currTree = new TreeNode(i);
                    currTree.left = left;
                    currTree.right = right;
                    allTrees.add(currTree);
                }
            }
        }
        return allTrees;
    }
}

3、时间复杂度

时间复杂度 ： O(nG_n)

对于n个节点生成的二叉搜索树数量等价于数学上第n个[卡特兰数]，卡特兰数用G_n表示，生成一颗二叉搜索树需要O(n)的时间复杂度，一共有G_n颗二叉搜索树，也就是O(nG_n)

空间复杂度： O(nG_n)

n个点生成的二叉搜索树有G_n颗，每颗有n个节点，因此空间复杂度为O(nG_n)。

三、总结

回溯和递归是穷举题目经常用到的算法，对于这道题来说。

我们只要找到所有的树的节点，然后递归着构造出所有左右子树的组合。

最后找出所有合法的二叉搜索树。