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 ListgenerateTrees(int n) { if (n == 0) return new ArrayList<>(); return generateBST(1, n); } private List generateBST(int left, int right) { List res = new LinkedList<>(); if (left > right) { // 划分不到的时候,这时候填null. res.add(null); return res; } for (int i = left; i <= right; i++) { List leftTrees = generateBST(left, i - 1); List 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]; }}