最近各大厂裁员裁的好慌，我还是刷起 leetcode 吧。弱鸡表示好忧虑。。

Leetcode 95

不同的二叉搜索树 II

输入: 3 输出:

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

解释: 以上的输出对应以下 5 种不同结构的二叉搜索树：

 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 

Leetcode 86

不同的二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 

题解

搜索二叉树(BST)的定义

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

给点一个数，去构造 BST. [1, 2, 3] 可以把这个数列做左子树和右子树的划分: [1] [2, 3] [1, 2] [3]

[1, 2] [2, 3] 又可以做左子树和右子树的划分.这是一个递归的过程. 把递归的结果构造起来,即可成为答案.

 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<TreeNode> generateTrees(int n) { if (n == 0) return new ArrayList<>(); return generateBST(1, n); } private List<TreeNode> generateBST(int left, int right) { List<TreeNode> res = new LinkedList<>(); if (left > right) { // 划分不到的时候,这时候填 null. res.add(null); return res; } for (int i = left; i <= right; i++) { List<TreeNode> leftTrees = generateBST(left, i - 1); List<TreeNode> rightTrees = generateBST(i + 1, right); for (TreeNode leftTree : leftTrees) { for (TreeNode rightTree : rightTrees) { // 注意,每个循环都要构造新的节点,不能在 for 循环外面生成. TreeNode root = new TreeNode(i); root.left = leftTree; root.right = rightTree; res.add(root); } } } return res; } } 

如果只需要数目,不需要生成具体的 BST 的话,只要能求出左子树有几种构造,右子树有几种构造,就可以最终确定.

而确定左子树和右子树的问题的时候,又可以划分为子问题. eg: 求 [1,2,3,4] 依赖于: [1,2,3] [2,3,4] 又依赖于: [1,2] [2,3] [3,4]的构造有几种.

class Solution { public int numTrees(int n) { int[] res = new int[n + 2]; res[0] = 1; res[1] = 1; // 没有左子树和右子树 res[2] = 2; for (int i = 3; i <= n; i++) { // 从 3 求到 n for (int j = 1; j <= i; j++) { // 求解过程中,需要依赖于之前的解,状态转移方程为每一种划分的左子树和右子树的构造方法乘积. res[i] += res[j - 1] * res[i - j]; } } return res[n]; } }