95. 不同的二叉搜索树

题目95 不同的二叉搜索树

https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

这个题目相比问题96就要复杂一些，问题96中我们不关心二叉搜索树的具体形态，只关心可能的数量，而问题95这里就必须要处理二叉搜索树具体的形态了。

这个题目给人感觉很复杂的样子，对于这种没有太好入手点的题目，先考虑最简单的情况，由小到大的思考解题方法。对于这个题目而言，如果n=1，那么很简单一个单节点的树就可以了。如果n=2呢？也很简单，要么把节点2作为节点1的右子树，要么把节点1作为节点2的左子树。进一步的，如果n=3呢？更进一步的，如果我们有了n=k的解，如何得到n=k+1的解呢？简单来说，就是把一个值为k+1的新节点依次加到n=k的解包含的每颗树上就可以了，对吧？那么给定n=k的解的一颗树，怎么把新节点k+1加到这颗树上，并且保持二叉搜索树的结构呢？因为新节点k+1最大，所以得从右子树入手。原树从根节点沿右子树一直走下去直到null节点，用新节点依次占据这条路径上每个节点的位置，被占据的节点作为新节点k+1的左子树即可。从直觉上，我觉得这样操作就是对的，虽然数学证明我是做不来的。

	public List<TreeNode> generateTrees(int n) {
		assert n >= 1 && n <= 8;

		List<TreeNode> ret = new ArrayList<>();
		ret.add(new TreeNode(1));

		for (int i = 2; i <= n; i++) {
			List<TreeNode> newRet = new ArrayList<>();

			for (TreeNode node : ret) {
				newRet.addAll(addNewNode(node, i));
			}

			ret = newRet;
		}

		return ret;
	}

	private List<TreeNode> addNewNode(TreeNode node, int val) {
		List<TreeNode> ret = new ArrayList<>();

		int depth = getDepthOfRightestNode(node);

		for (int i = 0; i <= depth; i++) {
			TreeNode copy = copy(node);
			TreeNode prev = null, cur = copy;

			int j = 0;
			while (j++ < i) {
				prev = cur;
				cur = cur.right;
			}

			TreeNode newVal = new TreeNode(val);
			newVal.left = cur;
			if (prev == null) {
				ret.add(newVal);
			} else {
				prev.right = newVal;
				ret.add(copy);
			}
		}

		return ret;
	}

	private int getDepthOfRightestNode(TreeNode node) {
		int depth = 0;
		while (node != null) {
			depth++;
			node = node.right;
		}

		return depth;
	}

	private TreeNode copy(TreeNode node) {
		if (node == null) {
			return null;
		}

		TreeNode copy = new TreeNode(node.val);
		copy.left = copy(node.left);
		copy.right = copy(node.right);

		return copy;
	}

这种方法是没有问题的，效率也不错，就是代码乍一看不够简洁，那么有没有更简洁的解法呢？参考官方题解我又下了下面一版使用递归的解法。递归解法也不难理解，从递归函数的形式就能理解解题思路。

	public List<TreeNode> generateTrees(int n) {
		assert n >= 1 && n <= 8;

		return generateTrees(1, n);
	}

	private List<TreeNode> generateTrees(int x, int y) {
		if (x > y) {
			List<TreeNode> trees = new ArrayList<>();
			trees.add(null);
			return trees;
		}

		List<TreeNode> trees = new ArrayList<>();
		for (int i = x; i <= y; i++) {
			List<TreeNode> leftTrees = generateTrees(x, i-1);
			List<TreeNode> rightTrees = generateTrees(i+1, y);

			for (TreeNode left : leftTrees) {
				for (TreeNode right : rightTrees) {
					TreeNode root = new TreeNode(i);
					root.left = left;
					root.right = right;
					trees.add(root);
				}
			}
		}

		return trees;
	}

在调试递归解法的过程中，发现有很多重复计算，稍作分析就想到，这不是正合适用动态规划么。于是又写了下面一版。有点奇怪的是，动态规划这一版时间效率最差。另外，因为Java不支持范型数组，所以代码看起来比较丑。

	public List<TreeNode> generateTrees(int n) {
		assert n >= 1 && n <= 8;

		List[][] dp = new List[n+1][n+1]; // dp[i..j] represents the BSTs for i..j
		for (int i = 1; i <= n; i++) {
			dp[i][i] = Arrays.asList(new TreeNode(i));
		}

		for (int step = 1; step <= n-1; step++) {
			for (int i = 1; i <= n - step; i++) {
				List<TreeNode> trees = new ArrayList<>();

				for (int k = i; k <= i+step; k++) {
					TreeNode root = new TreeNode(k);

					List leftTrees = new ArrayList();
					leftTrees.add(null);
					if (k-1 >= i) {
						leftTrees = dp[i][k-1];
					}

					List rightTrees = new ArrayList();
					rightTrees.add(null);
					if (k+1 <= i+step) {
						rightTrees = dp[k+1][i+step];
					}

					for (Object left : leftTrees) {
						for (Object right : rightTrees) {
							root.left = (TreeNode) left;
							root.right = (TreeNode) right;
							trees.add(copy(root));
						}
					}
				}

				dp[i][i+step] = trees;
			}
		}

		return dp[1][n];
	}

	private TreeNode copy(TreeNode node) {
		if (node == null) {
			return null;
		}

		TreeNode copy = new TreeNode(node.val);
		copy.left = copy(node.left);
		copy.right = copy(node.right);

		return copy;
	}

在 LeetCode 查看