手把手带你刷二叉搜索树(第三期)

2021年11月24日 阅读数:2
这篇文章主要向大家介绍手把手带你刷二叉搜索树(第三期),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

 

https://labuladong.gitee.io/algo/2/18/26/java

 

读完本文,你不只学会了算法套路,还能够顺便去 LeetCode 上拿下以下题目:git

96.不一样的二叉搜索树(Easy)算法

95.不一样的二叉搜索树II(Medium)函数

———–oop

以前写了两篇手把手刷 BST 算法题的文章, 第一篇 讲了中序遍历对 BST 的重要意义, 第二篇 写了 BST 的基本操做。ui

本文就来写手把手刷 BST 系列的第三篇,按部就班地讲两道题,如何计算全部合法 BST。spa

第一道题是力扣第 96 题「不一样的二叉搜索树」,给你输入一个正整数 n,请你计算,存储 {1,2,3...,n} 这些值共有有多少种不一样的 BST 结构。code

函数签名以下:blog

int numTrees(int n); 

好比说输入 n = 3,算法返回 5,由于共有以下 5 种不一样的 BST 结构存储 {1,2,3}递归

这就是一个正宗的穷举问题,那么什么方式可以正确地穷举合法 BST 的数量呢?

咱们前文说过,不要小看「穷举」,这是一件看起来简单可是比较有技术含量的事情,问题的关键就是不能数漏,也不能数多,你咋整?

以前 手把手刷二叉树第一期 说过,二叉树算法的关键就在于明确根节点须要作什么,其实 BST 做为一种特殊的二叉树,核心思路也是同样的。

举个例子,好比给算法输入 n = 5,也就是说用 {1,2,3,4,5} 这些数字去构造 BST。

首先,这棵 BST 的根节点总共有几种状况?

显然有 5 种状况对吧,由于每一个数字均可以做为根节点。

好比说咱们固定 3 做为根节点,这个前提下能有几种不一样的 BST 呢?

根据 BST 的特性,根节点的左子树都比根节点的值小,右子树的值都比根节点的值大。

因此若是固定 3 做为根节点,左子树节点就是 {1,2} 的组合,右子树就是 {4,5} 的组合。

左子树的组合数和右子树的组合数乘积就是 3 做为根节点时的 BST 个数。

咱们这是说了 3 为根节点这一种特殊状况,其实其余的节点也是同样的。

那你可能会问,咱们能够一眼看出 {1,2} 和 {4,5} 有几种组合,可是怎么让算法进行计算呢?

其实很简单,只须要递归就好了,咱们能够写这样一个函数:

// 定义:闭区间 [lo, hi] 的数字能组成 count(lo, hi) 种 BST
int count(int lo, int hi); 

根据这个函数的定义,结合刚才的分析,能够写出代码:

/* 主函数 */
int numTrees(int n) { // 计算闭区间 [1, n] 组成的 BST 个数 return count(1, n); } /* 计算闭区间 [lo, hi] 组成的 BST 个数 */ int count(int lo, int hi) { // base case if (lo > hi) return 1; int res = 0; for (int i = lo; i <= hi; i++) { // i 的值做为根节点 root int left = count(lo, i - 1); int right = count(i + 1, hi); // 左右子树的组合数乘积是 BST 的总数 res += left * right; } return res; } 

注意 base case,显然当 lo > hi 闭区间 [lo, hi] 确定是个空区间,也就对应着空节点 null,虽然是空节点,可是也是一种状况,因此要返回 1 而不能返回 0。

这样,题目的要求已经实现了,可是时间复杂度很是高,确定存在重叠子问题。

前文动态规划相关的问题屡次讲过消除重叠子问题的方法,无非就是加一个备忘录:

// 备忘录
int[][] memo;

int numTrees(int n) { // 备忘录的值初始化为 0 memo = new int[n + 1][n + 1]; return count(1, n); } int count(int lo, int hi) { if (lo > hi) return 1; // 查备忘录 if (memo[lo][hi] != 0) { return memo[lo][hi]; } int res = 0; for (int mid = lo; mid <= hi; mid++) { int left = count(lo, mid - 1); int right = count(mid + 1, hi); res += left * right; } // 将结果存入备忘录 memo[lo][hi] = res; return res; } 

这样,这道题就彻底解决了。

那么,若是给一个进阶题目,不止让你计算有几个不一样的 BST,而是要你构建出全部合法的 BST,如何实现这个算法呢?

这道题就是力扣第 95 题「不一样的二叉搜索树 II」,让你构建全部 BST,函数签名以下:

List<TreeNode> generateTrees(int n); 

好比说输入 n = 3,算法返回一个列表,列表中存储着以下五棵 BST 的根节点:

明白了上道题构造合法 BST 的方法,这道题的思路也是同样的:

一、穷举 root 节点的全部可能。

二、递归构造出左右子树的全部合法 BST。

三、给 root 节点穷举全部左右子树的组合。

咱们能够直接看代码:

/* 主函数 */
public List<TreeNode> generateTrees(int n) { if (n == 0) return new LinkedList<>(); // 构造闭区间 [1, n] 组成的 BST return build(1, n); } /* 构造闭区间 [lo, hi] 组成的 BST */ List<TreeNode> build(int lo, int hi) { List<TreeNode> res = new LinkedList<>(); // base case if (lo > hi) { res.add(null); return res; } // 一、穷举 root 节点的全部可能。 for (int i = lo; i <= hi; i++) { // 二、递归构造出左右子树的全部合法 BST。 List<TreeNode> leftTree = build(lo, i - 1); List<TreeNode> rightTree = build(i + 1, hi); // 三、给 root 节点穷举全部左右子树的组合。 for (TreeNode left : leftTree) { for (TreeNode right : rightTree) { // i 做为根节点 root 的值 TreeNode root = new TreeNode(i); root.left = left; root.right = right; res.add(root); } } } return res; } 

这样,两道题都解决了。

_____________